Математики помогите
Есть метод генерации псевдослучайных чисел.
Вкраце "n+1 число" = ("n число" * А + С) % М, где А, С, М, "первое число" это случайные числа (которые берутся хз откуда).
Суть задачи: мы знаем первые 4 числа (157, 5054, 25789, 13214). надо предсказать пятое (16605). Путём брутфорса я получил 13 комбинаций из которых 5 число предсказал правильно только 1. То есть если бы была возможность предсказывать шестое число по первым 5, то всё было бы ок.
Читая различные материалы по взлому данного метода я понял что нихрена не понял, везде приводят систему уравнений (например) на которую у меня не хватает интеллекта. Университетов не кончал, посему решил открыть вопрос на реакторе. Умы реактора, кто сможет решить, ваши варианты?
Еще на тему
Недостаточно четко?
% - это деление или целая часть, или что?
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. Нужны просто ответы или само решение?
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
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% угадать следующее число все еще нет.