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

Генератор псевдовипадкових чисел ('ГПВЧ, англ. pseudorandom number generator, PRNG) — це алгоритм або пристрій, який за допомогою детермінованої процедури та початкового значення (зерна, англ. seed) породжує послідовність чисел, що за своїми статистичними властивостями наближається до послідовності істинно випадкових чисел.

Істинно випадкові числа отримують з фізичних процесів, що вважаються непередбачуваними (тепловий шум, радіоактивний розпад, квантові ефекти тощо), і такі генератори називають генераторами істинно випадкових чисел (англ. true random number generator, TRNG). Псевдовипадкові генератори натомість повністю детерміновані: однакове початкове зерно відтворює ту саму послідовність, але при належному виборі алгоритму ця послідовність проходить складні статистичні тести та є достатньо «випадковою» для більшості прикладних задач.

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

Псевдовипадкові числа широко застосовуються в методі Монте-Карло та інших чисельних методах моделювання, у статистиці, комп’ютерній графіці та іграх, у криптографічних протоколах (для генерації ключів, ініціалізаційних векторів, nonce тощо), при тестуванні програмного забезпечення та в інших галузях, де потрібні відтворювані, але статистично якісні послідовності випадкових значень.

Мультиплікативний конгруентний метод (англ. multiplicative congruential generator, MCG, або генератор Лемера) є окремим випадком лінійного конгруентного генератора, у якому доданок дорівнює нулю. Рекурентна формула має вигляд

${\displaystyle x_{n+1}=(ax_{n}){\bmod {m}}}$,

де ${\displaystyle m}$ — модуль, ${\displaystyle a}$ — множник, а ${\displaystyle x_{0}}$ — початкове значення (зерно). Для фіксованих ${\displaystyle a}$ і ${\displaystyle m}$ така схема визначає дискретну динамічну систему з періодичною траєкторією; при вдалому виборі параметрів період послідовності наближається до ${\displaystyle m-1}$.

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

Класичний приклад — так званий minimal standard генератор Парка — Міллера з параметрами ${\displaystyle m=2^{31}-1}$ і ${\displaystyle a=16807}$, який довгий час використовувався в чисельних симуляціях.

Як просту ілюстрацію можна розглянути ${\displaystyle m=9}$, ${\displaystyle a=2}$, ${\displaystyle x_{0}=1}$: послідовність значень ${\displaystyle x_{n}}$ дорівнює ${\displaystyle 2,4,8,7,5,1,\dots }$ і має період 6. Переваги методу — простота реалізації та висока швидкодія; недоліки — відносно невеликий період і помітні кореляції між послідовними значеннями для невдалих параметрів, що обмежує застосування в задачах, чутливих до якості випадковості, зокрема в криптографії.

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

${\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}$

Змішаний конгруентний метод (англ. mixed congruential generator) відповідає загальному випадку лінійного конгруентного генератора з ненульовим доданком. Рекурентна формула має вигляд

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

де ${\displaystyle m}$ — модуль, ${\displaystyle a}$ — множник, ${\displaystyle c}$ — доданок (інкремент), а ${\displaystyle x_{0}}$ — зерно. При певних умовах на параметри (теорема Галла — Добелла) такий генератор має повний період довжини ${\displaystyle m}$ для будь-якого початкового значення.

Змішані конгруентні генератори історично були одними з найпоширеніших завдяки простоті та швидкості, і реалізовувалися в стандартних бібліотеках багатьох мов програмування (зокрема як функції типу rand()). Однак якість згенерованих послідовностей сильно залежить від вибору параметрів: невдалі набори ${\displaystyle a}$ і ${\displaystyle m}$ призводять до короткого періоду та сильної кореляції між багатовимірними точками, що може спотворювати результати моделювання. Через це в сучасних застосуваннях для серйозних наукових симуляцій рекомендують використовувати більш сучасні генератори або ретельно підібрані параметри LCG.

Квадратичний конгруентний метод' (англ. quadratic congruential generator, QCG) узагальнює лінійний конгруентний підхід шляхом додавання квадратного члена. Рекурентне співвідношення можна записати як

${\displaystyle x_{n+1}=(ax_{n}^{2}+bx_{n}+c){\bmod {m}}}$,

де ${\displaystyle a}$, ${\displaystyle b}$, ${\displaystyle c}$ — цілі коефіцієнти, ${\displaystyle m}$ — модуль, а ${\displaystyle x_{0}}$ — початкове значення. Уведення квадратичного члена ускладнює аналіз і може покращувати деякі статистичні властивості порівняно з простими LCG, проте повністю не усуває лінійних кореляцій у багатовимірному просторі.

Квадратичні конгруентні генератори детально досліджувалися в контексті теорії рівномірного розподілу та криптоаналізу, але на практиці використовуються рідше, ніж мультиплікативні й змішані конгруентні генератори або сучасніші схеми на основі регістрів зсуву. Їхні переваги — відносна простота реалізації та можливість отримати довші періоди для деяких модулів; до недоліків належать складніший аналіз якості та наявність ефективних атак у разі використання в криптографічних протоколах.

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

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

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

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

${\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). Початкові значення можна задавати довільні. Алгоритм може бути застосований в прикладних науках, але він має нижчу швидкість.

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

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

Огляд поширених алгоритмів

Лінійні конгруентні генератори (LCG)

Лінійний конгруентний генератор задається рекурентним співвідношенням ${\displaystyle x_{n+1}=(ax_{n}+c){\bmod {m}}}$. Це один із найстаріших і найпростіших класів ГПВЧ: реалізація потребує лише однієї операції множення, додавання та обчислення остачі. Переваги LCG — висока швидкодія та малий обсяг стану; недоліки — сильні кореляції у багатовимірному просторі й чутливість якості до вибору параметрів. Такі генератори часто застосовувалися в ранніх симуляційних пакетах і стандартних бібліотеках мов програмування, але нині вважаються застарілими для вимогливих статистичних задач.

Mother-of-All (генератори типу multiply-with-carry)

Під назвою Mother-of-All описують сімейство генераторів Джорджа Марсальї, основаних на методі multiply-with-carry (MWC). Стан генератора складається з кількох попередніх значень і «переносу», а нове значення обчислюється як лінійна комбінація попередніх значень, помножена на константи, з урахуванням переносу. Такі генератори забезпечують дуже довгі періоди (до ${\displaystyle 2^{60}}$ і більше) та високу швидкодію, завдяки чому їх застосовують у комп’ютерних іграх і деяких симуляційних системах. Водночас вони не призначені для криптографічного використання й потребують ретельного добору параметрів, щоб успішно проходити сучасні статистичні тести.

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

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

До інших популярних класів ГПВЧ належать генератори на основі регістрів зсуву з лінійним зворотним зв’язком (LFSR) та їхні комбіновані схеми, лагові генератори Фібоначчі, багаторекурсивні конгруентні генератори, а також криптографічно стійкі генератори, що будуються на блокових шифрах, потокових шифрах або криптографічних геш-функціях. У виборі конкретного алгоритму враховують компроміс між швидкодією, обсягом стану, складністю реалізації та вимогами до статистичної якості послідовності.

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

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

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

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

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

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

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

Застосування

Метод Монте-Карло та чисельне моделювання

У методі Монте-Карло та пов’язаних із ним стохастичних алгоритмах генератори псевдовипадкових чисел використовують для моделювання випадкових подій, чисельного інтегрування, оптимізації та розв’язання диференціальних рівнянь. Якість ГПВЧ безпосередньо впливає на упередженість і дисперсію оцінок: поганий генератор може давати систематично перекручені результати, особливо в довготривалих симуляціях високої точності.

Криптографічні протоколи

У криптографії випадкові та псевдовипадкові числа використовують для формування ключів шифрування, генерації ініціалізаційних векторів, nonce та одноразових параметрів протоколів аутентифікації. Звичайні швидкі генератори (LCG, Mersenne Twister тощо) не забезпечують криптографічної стійкості, адже їхній внутрішній стан можна відновити за достатньо великою підпослідовністю вихідних значень. Тому для криптографії застосовують криптографічно стійкі генератори псевдовипадкових чисел (CSPRNG), які ґрунтуються на блокових і потокових шифрах, криптографічних геш-функціях або спеціалізованих конструкціях і часто комбінуються з фізичними генераторами істинно випадкових чисел.

Комп’ютерні ігри та процедурна генерація

У комп’ютерних іграх ПВЧ використовуються для моделювання випадкових подій (кидання «віртуальних кубиків», випадкова поведінка супротивників, дроп предметів тощо) та процедурної генерації рівнів, карт, ландшафтів і завдань. Використання детермінованого генератора із зафіксованим зерном дозволяє відтворювати один і той самий ігровий світ (наприклад, за «сидом» світу), що зручно як для розробників, так і для гравців. Вимоги до статистичної якості тут зазвичай м’якші, ніж у наукових симуляціях, але вища швидкодія має критичне значення.

Реалізація в мовах програмування

У більшості сучасних мов програмування стандартні бібліотеки містять як «звичайні» генератори загального призначення, так і окремі засоби для криптографічно стійкої випадковості.

У мові C стандартна функція rand() зазвичай реалізується як лінійний конгруентний генератор із 31-бітним станом, що вважається недостатнім для вимогливих задач моделювання. У C++ починаючи з C++11 стандартна бібліотека <random> містить низку генераторів, серед яких широко використовується std::mt19937 — реалізація Mersenne Twister MT19937 із періодом ${\displaystyle 2^{19937}-1}$.

Для криптографічних задач у C/C++ зазвичай звертаються до спеціалізованих бібліотек (OpenSSL, libsodium тощо), які надають CSPRNG поверх системних джерел випадковості. 

У Java клас java.util.Random реалізує 48-бітний лінійний конгруентний генератор і призначений для загальних задач моделювання та ігор, але не для криптографії. Для безпечної генерації випадкових чисел використовується клас java.security.SecureRandom, який звертається до криптографічно стійких алгоритмів і джерел ентропії операційної системи.

У Python модуль random за замовчуванням використовує генератор Mersenne Twister MT19937, а модуль secrets поверх os.urandom() надає інтерфейс до криптографічно стійкого джерела випадковості, рекомендованого для створення паролів, токенів та інших секретів. Такий поділ відображає загальну практику: швидкі генератори використовують для чисельних експериментів, тоді як CSPRNG застосовують у безпекових сценаріях.

Див. також

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