Генератор криптографічно стійких псевдовипадкових чисел

Можна створити таку послідовність чисел, властивості якої будуть схожі на властивості послідовності випадкових чисел. Такі послідовності називаються псевдовипадковими.

Вперше запропонував їх використовувати Джон фон Нейман у 1946 р. Його метод полягав в наступному: n-розрядне число підносилось до квадрата і з нього вибиралися середні n цифр. Метод був дуже недосконалий, послідовності майже завжди вироджувалися в нуль або зациклювалися з коротким періодом. Пізніше було запропоновано багато різних алгоритмів отримання псевдовипадкових чисел.

В основі програмних генераторів як правило лежать рекурентні формули. Як правило, вони генерують цілі числа рівномірно розподілені на відрізку від 0, до деякого максимального m. Щоб отримати числа з рухомою комою, рівномірно розподілені на [0,1), кожен отриманий результат ділять на m.

Лінійна змішана форма

${\displaystyle x_{i}=\left(a_{0}+\sum _{j=1}^{l}a_{j}x_{i-j}\right)\mod m}$

Ця формула має багато часткових випадків:

Мультиплікативний конгруентний метод

${\displaystyle x_{i}=(a_{1}x_{i-1})\mod m}$

Змішаний конгруентний метод

${\displaystyle x_{i+1}=(ax_{i}+c)\mod m}$

Квадратичний конгруентний метод

Огляд методів

Лінійний конгруентний метод

Докладніше: Лінійний конгруентний метод

Запропонований Д. Х. Лемером. Основна обчислювальна формула:

${\displaystyle x_{n+1}=(ax_{n}+c)\mod m}$

Алгоритм зациклюється з періодом, що не перевищує деякого m. Коефіцієнти а, m і x(0) можуть приймати довільні цілі значення, за винятком 0. Параметр с може бути також і 0, але в цьому випадку скорочується період. Число ітерацій m звичайно вибирається рівним максимальному значенню типу, що робить непотрібною операцію ділення, яка автоматично виконається при переповненні. Число а можна взяти рівним, наприклад, 1664525, с — рівним 1013904223. Такий метод часто реалізують в сучасних системах програмування, хоча він майже непридатний у галузі статистики чи криптографії, де вимоги до «випадковості» значно вищі.

«Mother-of-All» random number generator

Запропонований Джорджем Марсалією (Marsaglia), професором університету Флориди. Обчислювальна формула:

${\displaystyle {\begin{cases}S=21111111111x_{n-4}+1429x_{n-3}+1776x_{n-2}+5115x_{n-1}+c\\x_{n}={\frac {S}{2^{32}}}\\C=\left[{\frac {S}{2^{32}}}\right]\end{cases}}}$

Цей алгоритм є узагальненням попереднього і позбавлений його головного недоліку — короткого періоду. Його період — ${\displaystyle 2^{250}}$.

Випадкове число ${\displaystyle x_{i}}$ належатиме проміжку [0, 1). Початкові значення можна задавати довільні. Алгоритм може бути застосований в прикладних науках, але він має нижчу швидкість.

Вихор Мерсенна

Докладніше: Вихор Мерсенна

Вихор Мерсенна запропонований у 1997 Макуто Матсумото і Такеджі Нушиміро. Основна ідея полягає в тому, що до початкової ітерації, яка ініціює процедуру, застосовується серія бітових операцій. Після їх виконання отримують нову послідовність, перший член якої вважається псевдовипадковим числом. Цей алгоритм має величезний період: ${\displaystyle 2^{19937}-1}$ ітерації (це більше ніж ${\displaystyle 43\times 10^{6000}}$).

Алгоритм дуже швидкий через відсутність множень, але не має достатньої випадковості. Тому галузь застосування алгоритму дещо обмежена.

Генератори типу «Xorshift»

Одні з найновіших генераторів від Джорджа Марсалії. Знову розглядається деяка початкова послідовність, до якої застосовуються операції та побітові зсуви. Ці операції полягають в наступному:

${\displaystyle x_{n}=x_{n-1}{\mbox{ xor }}(x_{n-1}{\mbox{ shl }}a)\ }$

Замість shl можна використовувати також shr, та еквівалентне множення.

Алгоритм має період ${\displaystyle 2^{128}-1}$ та проходить тести Diehard.

Підсумкове випадкове число може бути одержано за допомогою підсумовування окремих членів послідовності, або застосування до них операції xor. В наш час^[] це один з найбільш вживаних алгоритмів; послідовність, що генерується, достатньо випадкова, періоди — від (залежно від реалізації), відсутність операцій множення позитивно позначається на швидкості.

Інші генератори

Інтерес можуть представляти комбінації вже представлених методів^[]. Деякі з них реалізовані у відповідних програмних середовищах у вигляді функцій rand(), random().

Randomize

Часто для створення унікальної послідовності псевдовипадкових чисел початковий її член ініціалізують наприклад остачею від ділення поточного часу в мілісекундах на певне число. Зазвичай це робить функція randomize(), хоча можна задати початкове число послідовності і вручну.

Див. також

• Випадкове просте число
• Рівномірно розподілена послідовність

Примітки

1. . Архів оригіналу за 21 вересня 2011. Процитовано 17 грудня 2010.{{}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title ()