Генерація випадкових чисел

Генерація випадкових чисел (англ. Random number generator; часто скорочується як RNG, ГВЧ) — це процес створення послідовності чисел або символів, що не має помітних або передбачуваних закономірностей. Хоча конкретна послідовність випадкових чисел може містити певні закономірності при аналізі, ці результати неможливо передбачити заздалегідь із ймовірністю, більшою за випадкову.

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

Апаратна(істинна) генерація випадкових чисел

Істинною генерацією випадкових чисел є генерація за допомогою апаратного генератору випадкових чисел (АГВЧ), основна ідея якої є генерація на основі результатів фізичних процесів. Така генерація використовує кінцевий набір даних, отриманих на виході фізичного генератора, для генерації довгої послідовності чисел шляхом перетворення вихідних чисел.

Найпростішим істинним генератором випадкових чисел є звичайні гральні кубики, які використовувалися в азартних та настільних іграх, а також у наукових дослідженнях. Подальшим розвитком апаратних ГВЧ стали лототрони, які механічно перемішують та витягують кульки з числами та обертові колеса рулетки. Для наукових цілей були створені машини які створювали таблиці з випадковими числами. Однак ці механічні метод є дуже повільними і не підходять для автоматичної генерації великих обсягів даних. Сучасні методи генерації спрямовані на рішення проблеми швидкості генерації використовуючи природну непередбачуваність як джерела ентропії. Основні джерела ентропії у ГВЧ поділяються на ті, які мають квантову природу та ті, які не використовують квантові процеси.

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

Оскільки деякі квантово-механічні процеси абсолютно випадкові, вони є «золотим стандартом» для АГВЧ. Явища, що використовуються в генераторах, включають:

• Дробовий шум— це шум в електричних ланцюгах, що викликаний дискретністю носіїв електричного заряду. Також цим терміном називають шум в оптичних приладах, що викликаний дискретністю переносника світла. В нашому випадку, як джерело шуму використовують фотоелектронний помножувач або електровакуумні фотоелементи .
• Радіоактивний розпад використовують як джерело шуму, оскільки для нього характерна випадковість кожного окремого акту розпаду. У результаті на приймач (наприклад, лічильник Гейгера або сцинтиляційний лічильник) у різні проміжки часу потрапляє різна кількість частинок.
• Спонтанне параметричне розсіяння також можна використовувати в генераторації випадкових чисел.

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

Неквантові явища простіше виявити, але АГВЧ, що засновані на них, будуть сильно залежати від температури (наприклад, величина теплового шуму пропорційна до температури навколишнього середовища). Серед процесів, що застосовують для створення АГВЧ, можна відзначити:

• Тепловий шум у резисторі, з якого після посилення виходить генератор випадкової напруги. Зокрема, генератор чисел у комп'ютері Манчестерська автоматична цифрова машина ґрунтувався на цьому явищі.
• Атмосферний шум, що його виміряв радіоприймач; сюди ж можна віднести й прийом космічних променів за допомогою приймача, кількість яких у різні проміжки часу випадкова.

Після отримання вихідного необробленого сигналу з фізичного джерела, АГВЧ використовує процесор ентропії. Його завдання — очистити вихідний сигнал від можливих зміщень та кореляцій, перетворюючи його на послідовність, максимально близьку до ідеальної випадковості. Це забезпечує надійність генератора, особливо для криптографічних застосувань. Головною перевагою АГВЧ є забезпечення істинної випадковості (ентропії), що робить їх незамінними для криптографічних застосувань, де передбачуваність є неприпустимою. Однак, швидкість генерації АГВЧ, як правило, значно нижча порівняно з генерацією псевдовипадкових чисел, оскільки вона обмежена фізичними процесами, з яких збирається ентропія. Це створює проблему, коли потрібна велика кількість випадкових чисел за короткий проміжок часу.

Програмна генерація псевдовипадкових чисел

Псевдовипадкові числа генеруються за допомогою комп'ютерних програм. Зазвичай такі програми базуються на деякій рекурентній формулі. Задаючи однакові початкові члени послідовності можна щоразу отримувати однакові послідовності. Числа які вони генерують називають «псевдовипадковими» бо вони отримуються за чітким детермінованим алгоритмом. Більшість програмних генераторів виробляють випадкові числа, рівномірно розподілені в інтервалі [0, 1]. Необхідність моделю­ваня таких чисел обумовлена тим, що на їх основі можна отримати випадкові числа практично будь-яких розподілів. Потрібно також мати на увазі, що випадкові числа, які виробляють програмні генератори, є квазірівномірно розподіленими. Причина в тому, що вони створюються комп'ю­тером, кількість двійкових розрядів якого обмежена, і за його допомогою можна зобразити тільки дискретні значення з діапазону від 0 до 1.

У більшості генераторів псевдовипадкових чисел X_S використовується реку­рентна процедура X_i+1 = f(X_i). Найпростішим та найдавнішим серед таких генера­торів є генератор Джона фон Неймана, робота якого базувалась на мето­ді середин квадратів. Візьмемо умовно довільне чотирирозрядне десяткове число як

$x_{1}x_{2}x_{3}x_{4}$

Підне­семо це число до квадрату

$x_{1}x_{2}x_{3}x_{4}$

$\times$

$x_{1}x_{2}x_{3}x_{4}$

$=$

$y_{1}y_{2}y_{3}y_{4}y_{5}y_{6}y_{7}y_{8}$

і в отриманому результаті відкинемо по дві цифри злі­ва і справа:

$y_{3}y_{4}y_{5}y_{6}$

Чотири цифри, які залишились, і є новим випадковим числом. Якщо результа­том множення є число з кількістю цифр менше восьми, зліва дописуються додат­кові нулі. Реалізувати програмно цей генератор дуже просто, але він має ряд вад:

• якщо початкове число парне, то може відбутися виродження послідовно­сті, тобто починаючи з деякого значення всі наступні дорівнюватимуть нулю.
• числа, які виробляє генератор, є сильно корельованими.

Більшість подальших алгоритмів генерування псевдовипадкових чисел базується на формулі

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

Вона використовує властивість конгруентності, яка полягає в тому, що два цілих числа А і В є конгруентними за модулем m, якщо їх різниця (А - В) є числом, яке ділиться на m без остачі (тобто є кратним m). Максимальна кількість чисел, яку може отримати формула, це модуль m . Рекурентне співвідношення можна поширити на матриці, щоб вони мали набагато довші періоди та кращі статистичні властивості.

Завдяки простоті обчислення за модулем, тривалий час лінійні конгурентні генерації (ЛКГ) були найбільш поширеним методом генерації псевдовипадкових чисел. Їхня перевага полягає у високій швидкості генерації та можливості досягнення максимально можливого періоду (рівного модулю m), якщо параметри обрані правильно. Однак вони мають значний недолік: отримані числа демонструють сильну кореляцію і недостатньо проходять суворі статистичні тести, особливо у старших бітах. Це обмежує їхнє застосування у високоточних симуляціях.

Для вирішення проблеми статистичної слабкості ЛКГ були розроблені складніші алгоритми. Найвідомішим і найбільш поширеним у наукових розрахунках та статистичному моделюванні є Генератор Вихрового Мерсенна. Цей алгоритм, розроблений у 1997 році, має надзвичайно великий період (2¹⁹⁹³⁷ - 1, що значно перевищує більшість ЛКГ) та високу швидкість. Його статистичні властивості є значно кращими, що робить його стандартом для багатьох програмних бібліотек.

Незважаючи на постійне вдосконалення, слід пам'ятати, що жоден генератор псевдовипадкових чисел не може створити істинно випадкову послідовність, оскільки всі вони є детермінованими (якщо відомі початкові дані, вся послідовність передбачувана). Це робить їх непридатними для прямого використання у криптографії, де непередбачуваність є абсолютною вимогою. Тому оцінка якості згенерованих чисел за допомогою статистичних тестів є обов'язковою.

Таблиці випадкових чисел

Табличні ГВЧ як джерело випадкових чисел використають спеціальним образом складені таблиці, що містять перевірені некорельовані, тобто ніяк не залежний один від одного, цифри. Такі таблиці заповнюються реалізаціями випадкової величини з заданим розподілом. Представлені у таких таблицях вибірки дуже якісні, та вони мають обмежений розмір. Кількість таких вибірок невелика, що суттєво обмежує їх використання. Перевага цього методу в тому, що він дає дійсно випадкові числа, тому що таблиця містить перевірені некорельовані цифри. Недоліком методу є те, що для зберігання великої кількості цифр потрібно багато пам'яті, а також більші труднощі породження й перевірки такого роду таблиць, повтори при використанні таблиці вже не гарантують випадковості числової послідовності, а виходить, і надійності результату.

Див. також

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

Посилання

• Numberator.com [Архівовано 9 грудня 2018 у Wayback Machine.] (Генерує мільйон випадкових серійних номерів і кодів за секунди. Доступна безкоштовна версія.)
• Генерація криптографічно безпечних випадкових чисел на Windows без використання CryptoAPI від MSDN
• RandomNumbers.info [Архівовано 7 серпня 2008 у Wayback Machine.] (випадкові числа, що генеруються, використовуючи елементарний процес квантової оптики)

Джерела

• Jacak, Marcin M.; Jóźwiak, Piotr; Niemczuk, Jakub; Jacak, Janusz E. (9 серпня 2021). Quantum generators of random numbers. Scientific Reports. 11 (1): 16108. doi:10.1038/s41598-021-95388-7. ISSN 2045-2322. PMC 8352985. PMID 34373502.
• Herrero-Collantes, Miguel; Garcia-Escartin, Juan Carlos (22 лютого 2017). Quantum random number generators. Reviews of Modern Physics (амер.). 89 (1). doi:10.1103/revmodphys.89.015004. ISSN 0034-6861. Архів оригіналу за 17 серпня 2025.
• Optica Publishing Group. opg.optica.org. Процитовано 27 листопада 2025.