Как можно предсказать генератор случайных чисел, возможно ли это?
А обратно можно, т.е. на основании полученных данных найти исходные?

На основе борльшой совокупности статистических данных предсказать можно, т.к. все эти числа все равно псевдослучайные и в конце концов начинают повторятся (возможно с очень длинным периодом). Об этом еще Кнут писал

Так он и есть псевдослучайный - при большом количестве данных количество нулевых битов равняется единичным.

Если известен вид генератора с точностью до коэффициентов, то можно (например, перебором).

Skajem tak, pereborom mojno v ljubom sluchae, t.k. period psevdosluchai'noi' posledovatel'nosti v komp'jutere ogranichen. Tol'ko esli znat' raspredelenie, kotoromu podchinjaetsja posledovatel'nost', to nai'ti chisla budet namnogo legche. Exhe ochen' pomoglo by, esli ty znal chast' posledovatel'nosti, kotoraja uje pojavilas' i metod generacii chisel.

Che-to ja prognal. Esli ty znaesh' metod i chislo posledovatel'nosti vmeste s ego indeksom, to mojno so-100% garantiei' ukazat' sledujuxhii' chlen posledovatelnosti.

Если ПСП формируется линейным рекуррентным регистром, то можно, если удастся за обозримое время решить большую систему уравнений.

Цитата

эти числа все равно псевдослучайные

а рнд это вообще очень поршивая штука.podval если ты мне напомнишь как это работает

Цитата

линейным рекуррентным регистром

то я подскажу как подобраться к решению задачи, я этим три года назад занимался в дипломной работе, но всех особенностей не помню

Не существует генераторов чисто случайных чисел, поведение которых не подчиняется конкретному закону генерирования случайной последовательности… Поэтому теоретически возможно предсказание работы генератора как по входу так и по выходу…

Цитата

Поэтому теоретически возможно предсказание работы генератора как по входу так и по выходу…

главное что бы данных было достаточно, а именно больше периода повторения

Расскажите устройство стандартного random()

насколько мне известно, стандартный random() реализован так:
x(n+1)=a*x(n)+b mod m

Цитата

x(n+1)=a*x(n)+b mod m

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

Цитата

до чегож плохой алгоритм

вообще я слышал, что его уже на что-то заменили, но точно знаю, что некоторое время назад он был и в Pascale, и в C.

Цитата

гораздо лучше регистр сдвига, тобишь двоичное гаммирования, как реализовывается точно не помню

что такое двоичное гаммирование, не знаю
а регистр сдвига вот: (это нам так рассказывали на криптологии)
x(n+1)=f(x(n),x(n-1),x(n-2),...,x(n-k))
соответственно линейный регистр сдвига (он же линейный рекуррентный регистр сдвига) - когда функция f линейна
все операции делаются по модулю m (а m часто берут 2^n)

Цитата

он был и в Pascale, и в C

И в BC3.1, и в TP7.0, и в VC6++, и Linux (соответсвенно, в perl, си, си++ под линух).

Цитата

до чегож плохой алгоритм

Отчего плохой ? Для алгоритма скринсейвера неплохой ? А для чего тогда плохой ?

Цитата

Для алгоритма скринсейвера неплохой ?

характеристики его плохие, плохое равномерное распределение дает.

Kak raz, ochen' daje ravnoverojatnoe. U Knuta v pervom tome jetot additivnyi' sposob byl razjevan.

Vot kak iz jetogo raspredelenija poluchit' drugoe - jeto vopros. Pravda summa jetih ravnoverojatnyh znachenii' daet priblijennoe normal'noe raspredelenie.

Цитата

Kak raz, ochen' daje ravnoverojatnoe. U Knuta v pervom tome jetot additivnyi' sposob byl razjevan.

а ты проверь

Vot proga:

Код

&#9553;void main(void) { &#9553;  randomize(); &#9553;  clrscr(); &#9553;  int counter[20]={0}, a; &#9553; &#9553;  for (int j=0; j<50; j++) &#9553;    for (int i=0; i<20; i++) &#9553;      counter[a=random(20)]++; &#9553;  cout<<endl; &#9553;  for (j=0; j<20; j++) { &#9553;    cout<<j<<" - "<<counter[j]<<" times"<<endl; &#9553;  } &#9553;}

A eto ee vyvod:

Цитата

0 - 53 times 1 - 48 times 2 - 58 times 3 - 40 times 4 - 49 times 5 - 42 times 6 - 42 times 7 - 57 times 8 - 48 times 9 - 47 times 10 - 47 times 11 - 55 times 12 - 56 times 13 - 49 times 14 - 45 times 15 - 50 times 16 - 44 times 17 - 59 times 18 - 50 times 19 - 61 times

Nu kak, ravnoverojatno?

Цитата

5 - 42 times 6 - 42 times

Цитата

9 - 47 times 10 - 47 times

двоичное гомирование дает более лучший результат

Цитата

двоичное гомирование дает более лучший результат

Privedi primer.

Tak jeto ja tol'ko 50x20 opytov proizvel, a esli 5000x100, to:

Цитата

0 - 54123 times 1 - 53438 times 2 - 53719 times 3 - 54698 times 4 - 52782 times 5 - 52844 times 6 - 53045 times 7 - 53141 times 8 - 53048 times 9 - 54174 times 10 - 54495 times 11 - 52740 times 12 - 52741 times 13 - 53326 times 14 - 53628 times 15 - 53242 times 16 - 52966 times 17 - 53140 times 18 - 53228 times 19 - 53322 times

Kak vidno dispersija men'she (otnositel'naja)

Цитата

Privedi primer.

напишу прогу. привиду

для скринсейвера алгоритм действительно неплохой
а вот, когда его начинают использовать для серьезных задач, проявляются его неприятные свойства
если смотреть распределение единичного случайного числа, то оно действительно очень близко к равномерному (как и показали приведенные здесь экспериментальные данные)
такие же результаты можно получить, если использовать такой вот алгоритм:
x(n+1)=x(n)+1 mod m
все дело в распределении вектора, состоящего из нескольких последовательно полученных значений
если генератор хороший, то они должны равномерно заполнять гиперкуб (ну с поправкой

прошу прощения, произошел несчастный случай - я случайно нажал на кнопку "отправить"...
так вот, этот реализации этого вектора должны заполнять этот куб равномерно.
вектор из двух значений будет удовлетворять одному и тому же линейному уравнению, которое и задает его работу
получается, что реализации вектора будут лежать на одной гиперплоскости, а значит, не заполнят куб равномерно.
если с помощью такого генератора выбирать ключи для какого-нибудь шифрования, можно сильно облегчить работу тем, кто ее будет взламывать...

Цитата

x(n+1)=a*x(n)+b mod m

кстати, а кто скажет какой период последовательности

не больше m (как и для всех регистров сдвига)
например, если a=1, b=1 - период максимален

Цитата

x(n+1)=x(n)+1 mod m

...Donald Knuth, vol.1

Цитата

гомирование

Позвольте поправить. Правильно так: ГАММИРОВАНИЕ, от слова ГАММА.

О линейном рекуррентном регистре (очень полезно почитать)
http://pitis.tsure.ru/files12/09.pdf

Цитата

не больше m  (как и для всех регистров сдвига)

либо ты не прав, либо алгоритм слишком галимый.....

Вот реализация Random(int) в Delphi 6:

считаем что символ PIC НЕопределен, на сколько я понял это под Kylix (GOT - global offset table, вроде это понятие из области unix-подобных систем)

{$IFDEF PIC}
function GetGOT: LongWord; export;
begin
asm
MOV Result,EBX
end;
end;
{$ENDIF}

procedure _RandInt;
asm
{ ->EAX Range }
{ <-EAX Result }
PUSH EBX
{$IFDEF PIC}
PUSH EAX
CALL GetGOT
MOV EBX,EAX
POP EAX
MOV ECX,[EBX].OFFSET RandSeed
IMUL EDX,[ECX],08088405H
INC EDX
MOV [ECX],EDX
{$ELSE}
// обнуляем EBX, зачем , можно просто IMUL EDX,[RandSeed],08088405H
XOR EBX, EBX
// перемножаем RandSeed и 134775813 (08088405H)
IMUL EDX,[EBX].RandSeed,08088405H
// увеличиваем на еденицу старшее двойное слово результата умножения
INC EDX
// сохраняем старшее двойное слово результата умножения как новый RandSeed
MOV [EBX].RandSeed,EDX
{$ENDIF}
// умножаем преданный в качестве параметра диапазон на старшее двойное слово предыдущего результата
MUL EDX
// берем старшее двойное слово от предыдущего умножения, это и будет результат
MOV EAX,EDX
POP EBX
end;

знающие люди напишите формулу чему равно a, b, m если это x(n+1)=a*x(n)+b mod m , или это что-то другое?
у мя не выходит, не дружен я с математикой

Цитата

либо ты не прав, либо алгоритм слишком галимый.....

часто в качестве m берут что-то вроде 2^32
по-моему, это совсем неплохо для периода

Цитата

// перемножаем RandSeed и 134775813 (08088405H) // увеличиваем на еденицу старшее двойное слово результата умножения // сохраняем старшее двойное слово результата умножения как новый RandSeed

это был бы в точности тот алгоритм, который и предполагается, если последние две операции выполнялись не над старшим dword, а над младшим.
в этом случае a=134775813, b=1, m=2^32
если все же операции выполнять над старшим словом, может получиться такая наприятная ситуация:
пусть RandSeed=1 (должно же такое бывать)
тогда 134775813*RandSeed=134775813
старшее dword результата произведения равно 0
тогда RandSeed=1
к сожалению, я не знаю этого ассемблера и ориентируюсь только по комментариям...

хм, я не много ошибся в разборе поцедуры. После первого умножения идет работа с младшим двойным словом. Вот верный вариант:

procedure _RandInt;
asm
{ ->EAX Range }
{ <-EAX Result }
PUSH EBX
{$IFDEF PIC}
PUSH EAX
CALL GetGOT
MOV EBX,EAX
POP EAX
MOV ECX,[EBX].OFFSET RandSeed
IMUL EDX,[ECX],08088405H
INC EDX
MOV [ECX],EDX
{$ELSE}
// обнуляем EBX, зачем , можно просто IMUL EDX,[RandSeed],08088405H
XOR EBX, EBX
// перемножаем RandSeed и 134775813 (08088405H)
IMUL EDX,[EBX].RandSeed,08088405H
// увеличиваем на еденицу младшее двойное слово результата умножения
INC EDX
// сохраняем младшее двойное слово результата умножения как новый RandSeed
MOV [EBX].RandSeed,EDX
{$ENDIF}
// умножаем преданный в качестве параметра диапазон на младшее двойное слово предыдущего результата
MUL EDX
// берем старшее двойное слово от предыдущего умножения, это и будет результат
MOV EAX,EDX
POP EBX
end;

Это сообщение отредактировал(а) cully - 22.3.2003, 03:45

и еще вопрос в догонку: чем обоснован выбор a=134775813?

От этого числа (в большей степени, чем от b) зависит равномерность распределения выходных значений. Если немного попреобразовывать эту формулу, можно прийти к линейному регистру сдвига:

x(n)=a*x(n-1)+b
x(n+1)=a*x(n)+b
b=x(n)-a*x(n-1)
x(n+1)=a*x(n)+x(n)-a*x(n-1)
-----------------------------------
x(n+1)=(a+1)*x(n)-a*x(n-1) [надеюсь я ничего не напутал ]
(только теперь надо задавать два начальных значения)

Линейные регистры сдвига довольно хорошо изучены. Известны зависимости некоторых показателей качества генерируемых ними последовательностей от коэффициентов линейного рагистра. Нам в институте дали только способ определения периода с помощью характеристических полиномов регистра, а показателей качества псевдослучайных последовательностей дали около десятка.
Думаю, обоснование выбора подобных чисел можно найти в книгах по криптологии или связанным с ней дисциплинам...
P.S.
А первое, что приходит в голову - a не должно быть делителем m (в нашем случае оно просто должно быть нечетным), но это - лишь первый шаг для сужения области поиска подходящих чисел

ок, все понятно, но вернемся к вопросу топика

есть у меня большая выборка значений (100 000) и что делать дальше? как построить гипотезу о вожмоном устройстве датчика? ... и предсказать следуещее 100 001 значение ?

Это сообщение отредактировал(а) cully - 23.3.2003, 10:34

наконец-то проделал несколько экспериментов
вот некоторые результаты:

У генератора x(n+1)=a*x(n)+b есть неприятная особенность: на каждом шаге меняется четность.
(это если "a" нечетное, иначе четность вообще меняться не будет)

Цитата

И в BC3.1, и в TP7.0, и в VC6++, и Linux (соответсвенно, в perl, си, си++ под линух).

Боюсь, что это не так. В BC++3.1 и в VC++6.0 генератор случайных чисел построен по-другому (к сожалению, не знаю как)
Этот генератор я обнаружил только в Delphi (наверное, он есть и в TP7.0, но я не проверял)
В C++ генератор другой, он не обладает вышеописанным свойством

Цитата

есть у меня большая выборка значений (100 000)

Для предсказания этого генератора нужно не больше трех последовательных чисел:
1, если известны a,b
2, если известно что-то одно
3, если оба коэффициента неизвестны

А вот, собственно, алгоритм предсказания:
x(n+1)=a*x(n)+b mod m
m=2^32
a=134775813
b=1

Возможны случаи, когда мы работаем с генератором, у которого другие коэффициенты:
тогда составляем систему уравнений, использующих несколько последовательных значений
из этой системы находим коэффициенты

Цитата

как построить гипотезу о вожмоном устройстве датчика

Скорее всего, нужно перебирать все известные гипотезы, пока одна не подойдет.

Состояние рассмотренного генератора полностью описывается его выходом (RandSeed)
Состояние любого реккурентного регистра полностью описывается несколькими последними выходами
Но ведь можно построить генератор, состояние которого будет скрыто, а за выход будет браться какая-то функция от состояния
такой генератор значительно сложнее взломать.
А еще достаточно добавить подходящую нелинейность, чтобы практически обезвредить весь линейный анализ.

Цитата

главное что бы данных было достаточно, а именно больше периода повторения

Конечно, если есть все данные за период, можно с легкостью предсказать каждое следующее значение. Однако, почти всегда период измеряется величинами порядка 2^32.

Вообще предсказание генераторов случайных чисел часто используется при взломе шифров, поэтому этих генераторов уже понапридумывали кучу, и характеристики у них значительно лучше, чем стандартных.

P.S.
извините за большой размер сообщения, оно все как-то само получилось

2maxim1000:Угу, именно этот способ я и имел в виду в начале дискуссии.

Цитата

Скорее всего, нужно перебирать все известные гипотезы, пока одна не подойдет.

По-моему здесь имелся в виду статистический анализ.

Цитата

QUOTE  И в BC3.1, и в TP7.0, и в VC6++, и Linux (соответсвенно, в perl, си, си++ под линух). Боюсь, что это не так. В BC++3.1 и в VC++6.0 генератор случайных чисел построен по-другому (к сожалению, не знаю как)

srand от VC6++:

Цитата

004027A0 55                  push        ebp 004027A1 8B EC                mov        ebp,esp 004027A3 8B 45 08            mov        eax,dword ptr [seed] 004027A6 A3 50 3A 42 00      mov        [holdrand (00423a50)],eax 004027AB 5D                  pop        ebp 004027AC C3                  ret

rand() от VC6++:

Цитата

004027B0 55                  push        ebp 004027B1 8B EC              mov        ebp,esp 004027B3 A1 50 3A 42 00      mov        eax,[holdrand (00423a50)] 004027B8 69 C0 FD 43 03 00  imul        eax,eax,343FDh 004027BE 05 C3 9E 26 00      add        eax,269EC3h 004027C3 A3 50 3A 42 00      mov        [holdrand (00423a50)],eax 004027C8 A1 50 3A 42 00      mov        eax,[holdrand (00423a50)] 004027CD C1 F8 10                sar        eax,10h 004027D0 25 FF 7F 00 00      and        eax,7FFFh 004027D5 5D                  pop        ebp 004027D6 C3                  ret

Другими словами, в VC6++ алгоритм у rand() такой:

seed' = ( seed * 0x343FD (знаковое умножение) + 0x269EC3 ) mod 2^32;

результат от ф-ции rand будет:

rand() = (seed' >> 16) & 7FFFh;

Если не веришь, задай конкретные значения в srand'е (0,1 ...) и проверь ;)

Тут пришел Chingachguk и все опошлил

Цитата

rand() = (seed' >> 16) & 7FFFh;

шутка?

Kstati, pro integral - ja ego privel k vidu gamma funkcii i poluchilos', chto ot 0 do +infinity budet 2 (=2*г(1)=2*0!=2)

Цитата

шутка?

Почему ?

mov eax,[holdrand (00423a50)] // eax = seed'
sar eax,10h // eax >> = 16
and eax,7FFFh // eax & = 0x7FFFh

Так что безо всяких шуток. И в BC3.1 то же самое. Проверь так:

max=0;
for (i=0;i<10000;i++)
{
randval= rand();
if max<randval max=randval;
}
printf("MaxRand=%u",randval);

А вот в linux совсем иначе: чаще всего процедуры типа drand/srand компилируются с дефайном MAX_BITS 48.

Цитата

Kstati, pro integral

Так то ж ... аналитически. И зачем gamma, если такая простая подинтегральная (exp(-const*t)) ?

Это сообщение отредактировал(а) Chingachguk - 24.3.2003, 22:28

Кстати, а какие способы оценки качества псевдослучайных последовательностей существуют?

Как, например, определить скоррелированность между последовательными значениями случайной величины? Почему то обычно оценивают взаимосвязь между различными случайными величинами (парная корреляция). Хотя, очевидно что при характеризации случайной величины важен не только вид
функции распределения (равномерное, нормальное ....) но и сгруппированость значений внутри последовательности.

Например, автокорреляционная функция:

Цитата

long AKF(byte *Data,int Size,int StartBytePos,int StartBytesSize) {   int  i,j;   int  Tay;   byte b;   int  bNorm[8*100];   int  f;   long Maxf=0;   int  SizeInBits=Size*8;   for (i=0;i<Size;i++)   {     b=Data[i];     for (j=0;j<8;j++)     {       if ((b&0x80)==0x80)         bNorm[i*8+j]=1;       else         bNorm[i*8+j]=-1;       b<<=1;     }   }   //bSum=0;   //for (i=0;i<Size*8;i++) bSum+=(bNorm[i])*(bNorm[i]);   for (Tay=StartBytePos*8;Tay<((StartBytePos+StartBytesSize)*8);Tay++)   {     f=0;     for (i=0;i<Size*8;i++) f+=(bNorm[i])*(bNorm[(i+Tay)%(SizeInBits)]);     if (f<0) f=-f;     Maxf+=f;   }   return(Maxf); }

Но это специфическая реализация (моя) для конкретного дела, так что лучше смотреть sources ;)

а как быть с "Алгоритм Л'Экюера, комбинирующий две последовательности" ?

http://algolist.manual.ru/maths/generator/lequer.php