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


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

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

Автор: Alex101 19.3.2003, 18:09
Так он и есть псевдослучайный - при большом количестве данных количество нулевых битов равняется единичным.

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

Автор: neutrino 19.3.2003, 19:00
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.

Автор: neutrino 19.3.2003, 19:11
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 20.3.2003, 01:44
Если ПСП формируется линейным рекуррентным регистром, то можно, если удастся за обозримое время решить большую систему уравнений.

Автор: Step 20.3.2003, 02:12
Цитата
эти числа все равно псевдослучайные
а рнд это вообще очень поршивая штука.podval если ты мне напомнишь как это работает
Цитата
линейным рекуррентным регистром
то я подскажу как подобраться к решению задачи, я этим три года назад занимался в дипломной работе, но всех особенностей не помню

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

Автор: Step 20.3.2003, 02:24
Цитата
Поэтому теоретически возможно предсказание работы генератора как по входу так и по выходу…
главное что бы данных было достаточно, а именно больше периода повторения

Автор: serious 20.3.2003, 03:30
Расскажите устройство стандартного random()

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

Автор: Step 20.3.2003, 04:25
Цитата
x(n+1)=a*x(n)+b mod m
до чегож плохой алгоритм, гораздо лучше регистр сдвига, тобишь двоичное гаммирования, как реализовывается точно не помню но могу найти, если кому надо пишите.

Автор: maxim1000 20.3.2003, 05:18
Цитата
до чегож плохой алгоритм

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

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

Автор: Chingachguk 20.3.2003, 17:32
Цитата

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


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

Цитата

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


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

Автор: Step 20.3.2003, 18:32
Цитата
Для алгоритма скринсейвера неплохой ?
характеристики его плохие, плохое равномерное распределение дает.

Автор: neutrino 20.3.2003, 19:43
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.

Автор: Step 20.3.2003, 19:57
Цитата
Kak raz, ochen' daje ravnoverojatnoe. U Knuta v pervom tome jetot additivnyi' sposob byl razjevan.
а ты проверь

Автор: neutrino 20.3.2003, 22:00
Vot proga:
Код

║void main(void) {
║  randomize();
║  clrscr();
║  int counter[20]={0}, a;
║
&#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?

Автор: Step 20.3.2003, 23:19
Цитата
5 - 42 times
6 - 42 times
Цитата
9 - 47 times
10 - 47 times

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

Автор: neutrino 21.3.2003, 00:40
Цитата
двоичное гомирование дает более лучший результат

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)

Автор: Step 21.3.2003, 00:44
Цитата
Privedi primer.
напишу прогу. привиду

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

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

Автор: Step 21.3.2003, 03:05
Цитата
x(n+1)=a*x(n)+b mod m
кстати, а кто скажет какой период последовательности

Автор: maxim1000 21.3.2003, 03:29
не больше m smile.gif (как и для всех регистров сдвига)
например, если a=1, b=1 - период максимален

Автор: neutrino 21.3.2003, 03:57
Цитата
x(n+1)=x(n)+1 mod m

...Donald Knuth, vol.1

Автор: podval 21.3.2003, 05:20
Цитата
гомирование

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

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

Автор: Step 21.3.2003, 18:57
Цитата
не больше m  (как и для всех регистров сдвига)
либо ты не прав, либо алгоритм слишком галимый.....

Автор: stab 22.3.2003, 01:51
Вот реализация 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, зачем confused.gif, можно просто 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;

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

Автор: maxim1000 22.3.2003, 02:44
Цитата
либо ты не прав, либо алгоритм слишком галимый.....

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

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

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

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

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;

Автор: stab 22.3.2003, 03:51
и еще вопрос в догонку: чем обоснован выбор a=134775813?

Автор: maxim1000 22.3.2003, 05:31
От этого числа (в большей степени, чем от 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) [надеюсь я ничего не напутал smile.gif ]
(только теперь надо задавать два начальных значения)

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

Автор: stab 23.3.2003, 10:33
ок, все понятно, но вернемся к вопросу топика smile.gif

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

Автор: maxim1000 23.3.2003, 23:05
наконец-то проделал несколько экспериментов
вот некоторые результаты:

У генератора 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 smile.gif
m=2^32
a=134775813
b=1

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

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

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

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

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

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

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

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

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

Цитата

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

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

Автор: Chingachguk 24.3.2003, 19:43
Цитата

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 ...) и проверь ;)

Автор: neutrino 24.3.2003, 20:08
Тут пришел Chingachguk и все опошлил smile.gif

Цитата

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)

Автор: Chingachguk 24.3.2003, 22:22
Цитата

шутка?


Почему ?

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)) ?

Автор: remax 20.4.2003, 18:44
Кстати, а какие способы оценки качества псевдослучайных последовательностей существуют?

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

Автор: Chingachguk 21.4.2003, 08:48
Например, автокорреляционная функция:

Цитата

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 ;)

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

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

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