Кто говорит, тот не знает
А кто знает, тот не говорит
Древне китайская мудрость
В этом тексте мы рассмотрим несколько теорий и реализаций генераторов
случайных чисел. Мы так же попробуем определить оптимальный с точки зрения
размера и скорости.
ГПСЧ (PRNG) это генераторы псевдо-случайных чисел.
Никакой детерминированный алгоритм не может генерировать полностью случайные
числа, а только лишь аппроксимировать некоторые свойства случайных чисел.
Ещё Джон фон Нейман говорил, что только лишь арифметическими методами случайное
число получить невозможно. Любой ГПСЧ с ограниченными ресурсами рано или поздно зацикливается. Большинство простых арифметических генераторов хотя и обладают большой
скоростью, но страдают от многих серьёзных недостатков:
- Слишком короткий период
- Последовательные значения не являются независимыми
- Некоторые биты "менее случайны", чем другие
- Неравномерное распределение
- Обратимость
В компиляторах широкое распространение получил линейный конгруэнтный метод.
Применяется в простых случаях и не обладает криптографической стойкостью.
Этот алгоритм заключается в итеративном применении следующей формулы:
X[k+1]=(a*X[k]+c) mod m
Этот алгоритм используется в ANSI-C. Рассмотрим его:
#define RAND_MAX 32767
unsigned long next=1;
int rand(void) {
next=next*1103515245m;
return((unsigned int)(next/65536)2768);
}
void srand(unsigned int seed) {
next=seed;
}
Где a > 0, c > 0, m > 0 - некоторые целочисленные константы. Получаемая
последовательность зависит от выбора стартового числа X0 и при разных его
значениях получаются различные последовательности случайных чисел. В то же
время, многие свойства последовательности Xk определяются выбором коэффициентов
в формуле и не зависят от выбора стартового числа. Ясно, что последовательность
чисел, генерируемая таким алгоритмом, периодична с периодом, не превышающим m.
При этом длина периода равна m тогда и только тогда, когда:
1) НОД(c,m) = 1 (т.е. c и m взаимно просты);
2) a - 1 кратно p для всех простых p - делителей m;
3) a - 1 кратно 4, если m кратно 4.
При реализации выгодно выбирать m = 2e, где e - число бит в машинном слове,
поскольку это позволяет избавиться от относительно медленной операции
приведения по модулю. Младшие двоичные разряды сгенерированных таким образом случайных чисел
демонстрируют поведение, далёкое от случайного, поэтому рекомендуется
использовать только старшие разряды. Для генерации числа в диапазоне *0 - 2^32 -1* достаточно простого
умножения на мультипликатор и сложения с инкрементом. Деление по модулю
будет произведено автоматически при переполнении. Значения
мультипликатора и инкремента для этого случая получены в исследованиях
D. Knuth и H.W. Lewis.
Они рекомендуют использовать следующие коэффициенты:
a = 1664525, c = 1013904223, m = 2^32
Вот этой формулой рекомендуют пользоваться для генерации 32 битного числа.
next=64525*next+1013904223;
Чем мы благодарно и воспользуемся, ниже приведен модуль на ассемблере
использующий линейный конгруэнтный алгоритм.
; ;
;%%%%%%%%%%%%%%%%%%%%;
; ГЕНЕРАТОР СЛУЧАЙНОГО ЧмСЛА V. 0.3 (x) 2004 СЛОН ;
; Линейный конгруэнтный генератор он не прошёл тест DIEHARD и не ;
; является криптостойким ;
;%%%%%%%%%%%%%%%%%%%%;
; Интервал: [0..eax-1] ;
;--------------------------------------------;
; Использование: call r_init ;
; mov eax,ГРАНИЦА
ИНТЕРВАЛА ;
; call brandom32 ;
;--------------------------------------------;
; Результат: число в интервале [0..ГРАНИЦА
ИНТЕРВАЛА] ;
;%%%%%%%%%%%%%%%%%%%%;
;---[Подпрограмма инициализации генератора случайных чисел]---;
r_init:
push ebp eax edx ; Сохраняем в стэке
ebp
; eax, edx
call __delta1_ ;
__delta1_: pop ebp ; Получение дельта смещения
sub ebp,offset __delta1_ ;
db 0fh,031h ; Получаем случайное зерно
mov rand_seed,eax ;
pop edx eax ebp ; Восстанавливаем
edx
; eax, ebp
ret ; Возврат из подпрограммы
;---[Подпрограмма генерации случаного
числа в диапазоне]---;
brandom32: ; Эта подпрограмма
; возвращает случайное число
; в диапазоне 0..eax-1
push edx ecx ebp ; Сохраняем в стэке
edx
; ecx, ebp
call __delta2_ ;
__delta2_: pop ebp ; Получение дельта смещения
sub ebp,offset __delta2_ ;
imul eax,eax,100 ; Умножаем eax на 100
push eax ; и сохраняем eax в стэке
call random32 ; Вызываем подпрограмму
; генерации случайного числа
xor edx,edx ; Обнуляем edx
pop ecx ; Восстанавливаем значение
; из стэка в ecx
div ecx ; Делим eax на ecx
xchg eax,edx ; Помещаем остаток в eax
xor edx,edx ; Обнуляем edx
push 100 ; Помещаем в ecx - 100
pop ecx ;
div ecx ; Делим eax на ecx
pop ebp ecx edx ; Восстанавливаем ebp,
ecx,
; edx
ret ; Возврат из подпрограммы
;---[Подпрограмма генерации случайного числа]---;
random32:
push ebp
call
__delta3_ ;
__delta3_: pop ebp ; Получение дельта смещения
sub ebp,offset __delta3_ ;
mov eax,12345678h ;
rand_seed= dword ptr $-4 ;
imul eax,00019660Dh ;
add eax,03C6EF35Fh ; Математические операции
mov [ebp+rand_seed],eax ; для получения случайного
shr eax,16 ; числа
imul eax,[esp+4] ;
pop ebp
retn ; Возврат из подпрограммы
;--------------------------------------------;
Метод Фибоначчи с запаздываниями (Lagged Fibonacci generator) - один из методов,
который используется для генерации псевдослучайных чисел.
Особенности распределения случайных чисел, выдаваемых линейным конгруэнтным
алгоритмом, делает невозможным их использование в статистических алгоритмах,
требующих высокого разрешения. Это происходит из-за малого периода и их
предсказуемости. Поэтому линейный
конгруэнтный метод практически не используется ни в статистике, ни в криптографии. Обычно вместо него используют
либо фибоначиевые алгоритмы (в английской литературе "Subtract-with-borrow
Generators" (SWBG)), либо "Linear feedback shift registers".
Так же широкое распространение получил "Mersenne twister",
разработанный в 1997 году Мацумото и Нишимурой. Выигрывает у других ГПСЧ
громадным периодом (2^19937-1) и быстрой генерацией случайных чисел.
Недостатком данного алгоритма является то, что существует возможность
охарактеризовать выдаваемую последовательность, как не случайную.
Именно по этой причине данный алгоритм не применим в криптографии.
Агнер Фог разработал библиотеку реализующую Mersenne twister на ассемблере.
Его домашняя страница находится по адресу: http://www.agner.org
До недавнего времени, оптимальным вариантом генерации псевдо случайных чисел
был алгоритм Джорджа Марсаглии, который использует метод умножения с переносом.
Называется алгоритм - "Marsaglia-Multicarry".
Данный алгоритм достаточно быстрый и имеет различные периоды начиная с
2^60. Для его использования данного алгоритма на языке программирования
С достаточно вставить эту функцию в начале программы:
//--------------------------------//
unsigned long mwc()
{
static unsigned long x3456789,
y=362436069,
z=77465321,
c=13579;
unsigned long long t;
tС6905990LL*x+c;
x=y;
y=z;
c=(t>>32);
return z=(t&0xffffffff);
}
//--------------------------------//
После этого используйте MWC() для генерации целого 32 битного числа.
Данная функция имеет период где-то 2^125. Она с лёгкостью прошла тесты DIEHARD
и единственным её недостатком является использование умножения,
которое значительно влияет на скорость работы данного ГПСЧ.
Вот её реализация на ассемблере:
; ;
;%%%%%%%%%%%%%%%%%%%%;
; ГЕНЕРАТОР СЛУЧАЙНОГО ЧмСЛА V. 0.41 (x) 2005 СЛОН ;
;%%%%%%%%%%%%%%%%%%%%;
; Интервал: [0..eax-1] ;
;--------------------------------------------;
; Используется алгоритм ГПСЧ Джорджа Марсаглии - "Multiply-With-Carry(MWC)"
;
; Данный алгоритм прошёл тест DIEHARD его период 2^125
;
;--------------------------------------------;
; Использование: call r_init ;
; mov eax, ГРАНИЦА
ИНТЕРВАЛА ;
; call brandom32 ;
;--------------------------------------------;
; Результат: число в интервале [0..ГРАНИЦА
ИНТЕРВАЛА] ;
;%%%%%%%%%%%%%%%%%%%%;
;---[Подпрограмма инициализации генератора случайных чисел]---;
r_init:
push ebp eax edx ; Сохраняем в стэке
ebp, eax, edx
call __delta1_ ;
__delta1_: pop ebp ; Получение дельта смещения
sub ebp,offset __delta1_ ;
db 0fh,031h ; Получаем случайное зерно
mov [ebp+x],eax ;
pop edx eax ebp ; Восстанавливаем edx,eax,ebp
ret ; Возврат из подпрограммы
;---[Подпрограмма генерации случаного чмсла в диапазоне]---;
brandom32: ; Эта подпрограмма
; возвращает
случайное число
; в диапазоне 0..eax-1
push edx ecx ebp ; Сохраняем в стэке
edx, ecx, ebp
call __delta2_ ;
__delta2_: pop ebp ; Получение дельта смещения
sub ebp,offset __delta2_ ;
imul eax,eax,100 ; Умножаем eax на 100
push eax ; и сохраняем eax в стэке
call random32 ; Вызываем подпрограмму
; генерации случайного числа
xor edx,edx ; Обнуляем edx
pop ecx ; Восстанавливаем значение
; из стэка в ecx
div ecx ; Делим eax на ecx
xchg eax,edx ; Помещаем остаток в eax
xor edx,edx ; Обнуляем edx
push 100 ; Помещаем в ecx - 100
pop ecx ;
div ecx ; Делим eax на ecx
pop ebp ecx edx ; Восстанавливаем
ebp, ecx, edx,
ret ; Возврат из подпрограммы
;---[Подпрограмма генерации случайного числа]---;
random32:
push edx ecx ;
push ebp ; Сохраняем регистры в стэке
call __delta3_ ;
__delta3_: pop ebp ; Получение дельта смещения
sub ebp,offset __delta3_ ;
mov eax,12345678 ;
x = dword ptr $-4 ;
shl eax,0bh
xor eax,[ebp+x]
mov edx,362436069
y = dword ptr $-4
mov [ebp+x],edx
mov ecx,521288629
z = dword ptr $-4
mov [ebp+y],ecx
mov ebx,88675123
w = dword ptr $-4
mov [ebp+z],ebx
mov edx,[ebp+w]
shr edx,13h
xor edx,[ebp+w]
xor edx,eax
shr eax,08h
xor edx,eax
mov [ebp+w],edx
mov eax,edx
pop ebp ;
pop ecx edx ebx
retn ; Возврат из подпрограммы
