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

Для начала, попробуем напрограммить что нибудь простое, нуууу например генератор псевдо случайных чисел. Сегодня поговорим про псевдо случайные числа и для чего они нужны, про реальный генератор случайных чисел будет отдельная статья. Ключевое слово тут "псевдо", так для чего он нужен?



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

Формула довольно проста: k_i=(a*k_i-1+b)mod g

где a и b - некие параметры создания псевдо случайного числа

k_i-1 - предыдущее число полученное этой формулой

g  - модуль, который к стати определяет максимальную цифру которую можно получить в генераторе минус 1. :)

Ну а теперь попробуем подставить в формулу какие нибудь числа и посмотреть что получиться, пусть a = 7, b = 3, g = 11(хотим получить псевдо рандом от 0 до 10), стартовое значение k = 1

10 = (7 * 1 + 3) mod 11 - K1

7 = (7 * 10 + 3) mod 11 - K2

8 = (7 * 7 + 3) mod 11 - K4

...

6 = (7 * 2 + 3) mod 11 - K9

1 = (7 * 6 + 3) mod 11 - K10 - на 10 итерации мы снова получили цифру 1 и теперь если мы сделаем одиннадцатую итерацию подставив 1 в формулу, то снова получим 10 как в первой итерации и главное цикл повториться.

Тем самым мы зная точные параметры a,b,g и стартовое значение k мы можем точно повторить весь цикл генерирования псевдо случайных чисел. Промежуток через какую итерацию начинает генерить туже последовательность, зависит от начальных параметров a,b,g, с ними можно поиграться и получить более длинную цепочку чисел или наоборот более короткую.

Ну а теперь самое интересное, код на асме который делает 10 итераций и генерирует цепочку псевдослучайных чисел с небольшими коментами.

.386
.model flat, stdcall
option casemap:none

; подключаем всякие либы, для этого проекта в принципе они и не нужны
include \masm32\include\windows.inc
include \masm32\macros\macros.asm
uselib kernel32, user32

; чтобы работал человечески invoke создаем прототип
Gen_Ps_Random    PROTO:DWORD ,:DWORD, :DWORD, :DWORD

;поехал говнокод :)
.code
start:
    mov        eax, 1 ;задали стартовое значение K
    mov        ecx, 0Ah ; задали счетчик для loop

next_cif:
    invoke     Gen_Ps_Random,eax, 7, 3, 11 ; вызываем процедурку с параметрами
    loop    next_cif ; закольцовываем
    
    invoke ExitProcess,0 ; корректно выходим после окончания безобразий
    
;процедурка которая считает по формуле
Gen_Ps_Random proc uses edx k:DWORD, a:DWORD, b:DWORD, g:DWORD
    
    mov        eax, a ; EAX=a
    mul        k ; помножили EAX на k
    add        eax, b ; прибавили к EAX b
    xor        edx, edx ; обнулили edx, чтобы корректно был взят модуль
    div        g ; берем модуль числа
    mov        eax, edx ; копируем модуль в eax 
    
    Ret
Gen_Ps_Random EndP

end start

Вот в принципе и все, дешева и сердито :) Ради интереса можно поиграться с числами a, b, g и обнаружить что хорошие псевдо случайные числа генерируются если использовать простые числа в параметрах переменных. :)