Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Генератор псевдо случайных чисел

Автор: mmvds 2.1.2008, 22:14

Решил подумать над задачей прогнозирования значений генераторов псевдослучайных чисел (ГПСЧ) для начала нашел статью на http://algolist.ru/maths/generator/standard.php по реализации ГПСЧ в стандартной библиотеке stdlib.h I(n+1)=(a*I(n)+c)(mod m) т.е. зная, например 4 значения из последовательности случайных чисел получаем систему уравнений: I(1)=x I(2)=(a*x+c)(mod m) I(3)=(a*((a*x+c)(mod m))+c)(mod(m)) I(4)=(a*(a*((a*x+c)(mod m))+c)(mod(m))+c)(mod m) Для которой можно найти значения коэффициентов a,c,m, а по ним соответственно определить и остальную часть последовательности. Для определения a,c,m кроме перебора пока ничего не придумал, но в памяти a,c,m могут иметь значения от -2^31 до 2^31-1, т.е. перебирать 2^96 вариантов, что даже для современных компьютеров будет очень долго, вот сейчас думаю, как максимально сократить данный перебор. Возможно у кого-нибудь есть какие предположения или просто станет интересно, кто что думает?

Автор: maxim1000 3.1.2008, 01:38

если, например, взять a=0, то все кроме первого значения будут равны c mod m, так что определить c и m не получится так что в общем случае такое решить не получится обычно, берут m=2^32, если мне не изменяет память тогда a стоит брать нечётным, иначе у результата последний бит будет всегда одинаковый (так он хотя бы меняться будет) да и вообще при известном m можно составить систему линейных уравнений и попробовать решить её (только там с обратимостью коэффициентов нужно быть осторожным)

Автор: mmvds 3.1.2008, 13:17

Ага, нашел константы, предложенные Park и Miller'ом, для достижения наиболее равномерного распределения: a=7^5=16807, m=2^31-1=2147483647 Пробывал брать такие константы и перебирать только С (2^32 вариантов), решение найдено не было, видимо константы a и m другие. По-видимому m количество возможных значений интервала случайных чисел, т.е. задается пользователем, например, при m=10 будут вычисляться псевдослучайные числа от 0 до 9 Если знать наверняка, например то, что m=2^31-1, т.е максимальному четырех битовому числу, то mod m от любого выражения будет то же самое выражение и рекуррентная формула упрощается до I(n+1)=a*I(n)+c Т.е. получаем систему I(1)=x I(2)=a*x+c I(3)=a*(a*x+c)+c Неизвестные только а и с Если бы задача была чисто математической, то все элементарно, получаем систему: I(2)=a*I(1)+c I(3)=a*I(2)+c вычитаем из первого второе, делим на I(1)-I(2) a=(I(2)-I(3))/(I(1)-I(2)), откуда получаем и с Но с машинной математикой не все так просто, например, рассмотрим частный случай: x=1442366880 684384293=a*1442366880+c 347453115=a*684384293+c a=0.444510446 c=43237147.51 Но видно, что числа получились не целыми, что уже противоречит условию, а все из-за того, что одно и то же число в машинной математике можно получить умножении или сложением разных чисел, вызвав переполнение из-за 4 байтового ограничения на целые числа. 1000 000 000 * 10 = не 10 000 000 000, а 1 410 065 412 (тот самый остаток от деления на 2^31-1), т.е одному и тому же числу соответствует множество 1 410 065 412=5 705 032 706=10 000 000 000 и т.д. Что показывает, что чисто математически, к сожалению, данная задача не решается :( Полный перебор значений a и c  2^64 вариантов, а если еще и m считать не известной, то 2^96. Чтобы сократить перебор необходим какой-нибудь оптимизационный критерий, пока не соображу, какой.

Автор: maxim1000 3.1.2008, 13:51

хм... если речь идёт о C-шном генераторе, то, насколько я понимаю, он немного сложнее на выходе там - 16-битное число (то ли старшая, то ли младшая часть) и это значительно усложняет его "взлом" Цитата(mmvds @  3.1.2008,  13:17 ) Но с машинной математикой не все так просто, например, рассмотрим частный случай: x=1442366880 684384293=a*1442366880+c 347453115=a*684384293+c a=0.444510446 c=43237147.51 эээ нее...  про арифметику действительных чисел стоит на время забыть здесь - несколько другие правила + определяется, как (a+b) mod m - как обратная операция к + * как (a*b)mod m / как обратная операция к * так вот с +,-,* всё, как обычно, если закрывать глаза на переполнение а вот с / - нет деление здесь нужно понимать именно по определению: x/y - такое число, которое при умножении на y даст x т.е. в простейшем варианте - имея числа x,y перебираем все числа из 0..m-1 и проверяем условие если рассматривать общий случай, может получиться и несколько ответов, и ни одного для простых m всё относительно неплохо - все деления дают предсказуемый результат: для y=0 нет ответов, для других - ровно один здесь m не простое - 2^32, так что такой гарантии нету однако, если y взаимно просто с m (в данном случае y - нечётное), то всё неплохо: поищи вычисление обатного числа с помощью алгоритма Евклида Добавлено через 44 секунды Цитата(mmvds @  3.1.2008,  13:17 ) Если знать наверняка, например то, что m=2^31-1, т.е максимальному четырех битовому числу, то mod m от любого выражения будет то же самое выражение и рекуррентная формула упрощается до I(n+1)=a*I(n)+c поправочка: для этого нужно, чтобы m было 2^32

Автор: mmvds 3.1.2008, 15:14

Т.е как я понял, перебор пойдет уже по числу m, чтобы получить целочисленные a и с, Евклидом сокращаем перебор. Собственно 2^32 не так и много, для начала попробую перебрать грубой силой. Попробую переосмыслить все написанное  Цитата поправочка: для этого нужно, чтобы m было 2^32  2^32 для беззнаковых целых чисел, т.е. от 0 до 2^32 я так думаю, что возможны и отрицательные значения того же С, т.е. от -2^31 до +2^31-1

Автор: maxim1000 3.1.2008, 20:36

Цитата(mmvds @  3.1.2008,  15:14 ) 2^32 для беззнаковых целых чисел, т.е. от 0 до 2^32 я так думаю, что возможны и отрицательные значения того же С, т.е. от -2^31 до +2^31-1 а... я имел в виду, что (-1) не нужно Цитата(mmvds @  3.1.2008,  15:14 ) Т.е как я понял, перебор пойдет уже по числу m, чтобы получить целочисленные a и с, Евклидом сокращаем перебор. Собственно 2^32 не так и много, для начала попробую перебрать грубой силой. без m найти точные значения может не получиться впрочем, в результате может оказаться набор возможных значений так это... C-шный генератор исследуется?

Автор: mmvds 4.1.2008, 22:19

Цитата(maxim1000 @  3.1.2008,  20:36 ) так это... C-шный генератор исследуется?  На паскале насколько мне известно такой же алгоритм, на нем и исследую.

Автор: maxim1000 5.1.2008, 19:30

по крайней мере, в стандартной библиотеке C генератор с усложнением: берётся только часть так что с прогнозом возникнут проблемы...

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)