Решил подумать над задачей прогнозирования значений генераторов псевдослучайных чисел (ГПСЧ)
для начала нашел статью на алголист по реализации ГПСЧ в стандартной библиотеке 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 вариантов, что даже для современных компьютеров будет очень долго, вот сейчас думаю, как максимально сократить данный перебор.

Возможно у кого-нибудь есть какие предположения или просто станет интересно, кто что думает?

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

да и вообще при известном m можно составить систему линейных уравнений и попробовать решить её (только там с обратимостью коэффициентов нужно быть осторожным)

Ага, нашел константы, предложенные 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.

Чтобы сократить перебор необходим какой-нибудь оптимизационный критерий, пока не соображу, какой.

хм... если речь идёт о C-шном генераторе, то, насколько я понимаю, он немного сложнее
на выходе там - 16-битное число (то ли старшая, то ли младшая часть)
и это значительно усложняет его "взлом"


эээ нее... 
про арифметику действительных чисел стоит на время забыть
здесь - несколько другие правила
+ определяется, как (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 секунды

поправочка: для этого нужно, чтобы m было 2^32

Т.е как я понял, перебор пойдет уже по числу m, чтобы получить целочисленные a и с, Евклидом сокращаем перебор.
Собственно 2^32 не так и много, для начала попробую перебрать грубой силой.
Попробую переосмыслить все написанное 


2^32 для беззнаковых целых чисел, т.е. от 0 до 2^32
я так думаю, что возможны и отрицательные значения того же С, т.е.
от -2^31 до +2^31-1

Это сообщение отредактировал(а) mmvds - 3.1.2008, 15:14

а... я имел в виду, что (-1) не нужно



без m найти точные значения может не получиться
впрочем, в результате может оказаться набор возможных значений

так это... C-шный генератор исследуется?

На паскале насколько мне известно такой же алгоритм, на нем и исследую.

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