Математики помогите / математика :: наука :: реактор помоги :: пидоры помогите (реактор помоги)

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

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

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


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

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



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


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


Подробнее

пидоры помогите,реактор помоги,реактор помоги,математика,наука,песочница
Еще на тему
Развернуть
Сайт веселого настроения, говорили они... Приходи подеградируем говорили они.... Я аж вспотел только читая условия...
ПОТИШЕ БРАТИШКА
В ЭТОЙ СИТУАЦИИ
wh-fan wh-fan 12.09.201915:58 ответить ссылка -1.7
И да, у тебя купон просрочен.
wh-fan wh-fan 12.09.201915:59 ответить ссылка 0.6
Условия заданы, но ты не сформулировал вопрос. Пожалуйста, четко сформулируй вопрос.
Konrart Konrart 12.09.201916:02 ответить ссылка 0.6
>Суть задачи: мы знаем первые 4 числа (157, 5054, 25789, 13214). надо предсказать пятое (16605).
Недостаточно четко?
suiginto suiginto 12.09.201916:37 ответить ссылка -1.3
А, С, М - константы?
% - это деление или целая часть, или что?
Kelmiir Kelmiir 12.09.201916:11 ответить ссылка 0.9
Это остаток от деления
157 - это зерно (стартовое значение без вычислений) или первый "продукт" алгоритма?
Старт
Проблема в том, что для однозначного решения нужно больше чисел. Для текущего условия существует 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. Нужны просто ответы или само решение?
Прошу прощения, я протупил. Вариантов комбинаций бесконечно много, они описываются формулами вида (в каждой группе можно подставлять любые целые 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
Ну если вкратце. Вся проблема этой задачи в модульной арифметике. Она ебанутая, потому что хз что с этим делать:
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% угадать следующее число все еще нет.
Gribs Gribs 13.09.201905:33 ответить ссылка 0.1
кстате забыл упомянуть, что М не больше 65000 (да , на деле может быть и больше, но мы их не рассматриваем.)
Ну тогда Empty Face запостил решение для M=32768. x=0, y=0.
Gribs Gribs 13.09.201922:10 ответить ссылка 0.0
Только зарегистрированные и активированные пользователи могут добавлять комментарии.
Похожие темы

Похожие посты
КУПОН
НА 1 помощь КУПОН
НА 1 помощь