Математики помогите / пидоры помогите :: реактор помоги :: математика :: наука :: песочница

пидоры помогитереактор помогиматематиканаукапесочница

Математики помогите

,пидоры помогите,реактор помоги,реактор помоги,математика,наука,песочница

Есть метод генерации псевдослучайных чисел.

Вкраце "n+1 число" = ("n число" * А + С) % М, где А, С, М, "первое число" это случайные числа (которые берутся хз откуда).

Суть задачи: мы знаем первые 4 числа (157, 5054, 25789, 13214). надо предсказать пятое (16605). Путём брутфорса я получил 13 комбинаций из которых 5 число предсказал правильно только 1. То есть если бы была возможность предсказывать шестое число по первым 5, то всё было бы ок.

Читая различные материалы по взлому данного метода я понял что нихрена не понял, везде приводят систему уравнений (например) на которую у меня не хватает интеллекта. Университетов не кончал, посему решил открыть вопрос на реакторе. Умы реактора, кто сможет решить, ваши варианты?

Сайт веселого настроения, говорили они... Приходи подеградируем говорили они.... Я аж вспотел только читая условия...

ПОТИШЕ БРАТИШКА
В ЭТОЙ СИТУАЦИИ,пидоры помогите,реактор помоги,реактор помоги,математика,наука,песочница

wh-fan

12.09.2019, 12:58

ссылка

-1,7

И да, у тебя купон просрочен.

wh-fan

12.09.2019, 12:59

ссылка

+0,6

Условия заданы, но ты не сформулировал вопрос. Пожалуйста, четко сформулируй вопрос.

Konrart

12.09.2019, 13:02

ссылка

+0,6

>Суть задачи: мы знаем первые 4 числа (157, 5054, 25789, 13214). надо предсказать пятое (16605).
Недостаточно четко?

suiginto

12.09.2019, 13:37

ссылка

-1,3

А, С, М - константы?
% - это деление или целая часть, или что?

Kelmiir

12.09.2019, 13:11

ссылка

+0,9

Это остаток от деления

suiginto

12.09.2019, 13:36

ссылка

+0,0

157 - это зерно (стартовое значение без вычислений) или первый "продукт" алгоритма?

hellknight

12.09.2019, 15:01

ссылка

+0,0

Старт

suiginto

12.09.2019, 17:03

ссылка

0,0

Проблема в том, что для однозначного решения нужно больше чисел. Для текущего условия существует 4 различные комбинации A/C/M, которые дадут 5-е число 16605, причём дальше последовательности (т.е. 6-е и последующие числа) во всех 4 случаях будут различаться:

A=31 C=187 M=32768
A=31 C=187 M=65536
A=31 C=187 M=131072
A=131103 C=131259 M=262144

Если же были бы даны просто первых четыре числа и надо было реально угадать 5-е по 4-м первым, то вариантов, вероятно, было бы ещё больше.

P.S. Нужны просто ответы или само решение?

Empty Face

12.09.2019, 15:11

ссылка

+0,4

Прошу прощения, я протупил. Вариантов комбинаций бесконечно много, они описываются формулами вида (в каждой группе можно подставлять любые целые x и y):

A = 262144 x + 131103
C = 262144 y + 131259
M = 262144

A = 131072 x + 31
C = 131072 y + 187
M = 131072

A = 65536 x + 31
C = 65536 y + 187
M = 65536

A = 32768 x + 31
C = 32768 y + 187
M = 32768

Empty Face

12.09.2019, 15:36

ссылка

0,0

Ну если вкратце. Вся проблема этой задачи в модульной арифметике. Она ебанутая, потому что хз что с этим делать:
x_{n+1} = (A * x_{n} + C) % M.

Эту задачу можно переписать в обычную арифметику
x_{n+1} + k_{n+1}*M = A*x{n} + C,
где k_{n+1} - какое-то целое число.

Первым делом хотелось бы как-то найти M. Штука долгая, но для начала мы берем два уравнения и вычитаем их
x_{n+1} + k_{n+1}*M = A*x_{n} + C,
x_{n+2} + k_{n+2}*M = A*x_{n+1} + C
==========>
dx_{n+1} + l_{n+1}*M = A*dx_{n}

где dx_{n+1} = x_{n+2} - x_{n+1}.

Таких уравнений может быть довольно много. Чем больше тем лучше. Из них ты можешь выбрать все пары:
dx_{n+1} + l_{n+1}*M = A*dx_{n}
dx_{m+1} + l_{m+1}*M = A*dx{m}
================>
dx_{n+1}*dx_{m} - dx_{m+1}*dx_{n} = M*(какая-то поебень, но целая)

Таким образом с каждой пары мы получим от такое выражение слева, оно будет чему-то равно. Наибольший общий делитель таких выражений - это и есть твое M. Тебе повезет если этот наибольший делитель будет простым. Если он не простое, то M может быть любым делителем этого числа. С известным М найти A и C довольно просто.

Теперь в применимости к твоей задаче: если у тебя есть 4 исходных числа (х), то из них строиться 3 разности (dx) которые заключены в двух уравнениях. По этим двум уравнением можно построить только одну оценку М, которая будет равна 491520000 = 2^18*3*5^4. Либо любому делителю из этой херни который больше самого большого записанного числа. Вариантов дохрена (по крайней мере пару десятков точно).

Тут на помощь на приходит 5 число, которое возволяет составить 3 уравнения и получить 3 разных оценки на М с наибольшим общим делителем 262144 = 2^18. Так как третее число у тебя 25к>2^14, то M может быть 2^15, 2^16, 2^17, 2^18. То есть шансов 100% угадать следующее число все еще нет.