Цей термін має також інші значення див. Генератор випадкових чисел.
Генератор псевдовипадкових чисел (ГПСЧ. Англ. Pseudorandom number generator. PRNG) - алгоритм. породжує послідовність чисел. елементи якої майже незалежні один від одного і підкоряються заданому розподілу (зазвичай рівномірному).
Сучасна інформатика широко використовує псевдовипадкові числа в самих різних додатках - від методу Монте-Карло і імітаційного моделювання до криптографії. При цьому від якості використовуваних ГПСЧ безпосередньо залежить якість одержуваних результатів. Ця обставина підкреслює відомий афоризм математика ORNL Роберта Кавью (англ.) Рос. «Генерація випадкових чисел занадто важлива, щоб залишати її на волю випадку».
Джерела випадкових чисел
Джерела справжніх випадкових чисел знайти вкрай важко. Фізичні шуми. такі, як детектори подій іонізуючої радіації. дробовий шум в резисторі або космічне випромінювання. можуть бути такими джерелами. Однак застосовуються такі пристрої в додатках мережевої безпеки рідко. Складнощі також викликають грубі атаки на подібні пристрої.
Криптографічні додатки використовують для генерації випадкових чисел особливі алгоритми. Ці алгоритми заздалегідь визначені і, отже, генерують послідовність чисел, яка теоретично не може бути статистично випадковою. У той же час, якщо вибрати хороший алгоритм, отримана чисельна послідовність - псевдовипадкових чисел - буде проходити більшість тестів на випадковість. Однією з характеристик такої послідовності є період повторення, який повинен бути більше робочого інтервалу, з якого беруться числа.
Генератор псевдовипадкових чисел включений до складу багатьох сучасних процесорів. наприклад, RdRand входить в набір інструкцій IA-32. [1]
Ніякої детермінований алгоритм не може генерувати повністю випадкові числа, він може тільки апроксимувати деякі їх властивості. Як сказав Джон фон Нейман. «Всякий, хто має схильність до арифметичним методам отримання випадкових чисел, грішний поза всяких сумнівів».
Будь ГПСЧ з обмеженими ресурсами рано чи пізно зациклюється - починає повторювати одну і ту ж послідовність чисел. Довжина циклів ГПСЧ залежить від самого генератора і становить близько 2 n / 2. де n - розмір внутрішнього стану в бітах, хоча лінійні конгруентні і LFSR -генератори володіють максимальними циклами близько 2 n. Якщо породжувана послідовність ГПСЧ сходиться до занадто коротким циклам, то такий ГПСЧ стає передбачуваним і непридатним для практичного застосування.
Більшість простих арифметичних генераторів хоча і володіють великою швидкістю, але страждають від багатьох серйозних недоліків:
- Занадто короткий період / періоди.
- Послідовні значення не є незалежними.
- Деякі біти «менш випадкові», ніж інші.
- Нерівномірний одномірний розподіл.
- Оборотність.
Зокрема, алгоритм RANDU. десятиліттями використовувався на основному комплекті. виявився дуже поганим [2] [3]. що викликало сумніви в достовірності результатів багатьох досліджень, які використовували цей алгоритм.
ГПСЧ з джерелом ентропії або ГСЧ
Нарівні з існуючою необхідністю генерувати легко відтворювані послідовності випадкових чисел, також існує необхідність генерувати абсолютно непередбачувані або просто абсолютно випадкові числа. Такі генератори називаються генераторами випадкових чисел (ГВЧ - англ. Random number generator, RNG). Так як такі генератори найчастіше застосовуються для генерації унікальних симетричних і асиметричних ключів для шифрування, вони найчастіше будуються з комбінації криптостійкого ГПСЧ і зовнішнього джерела ентропії (і саме таку комбінацію тепер і прийнято розуміти під ГСЧ).
Майже всі великі виробники мікрочіпів поставляють апаратні ГВЧ з різними джерелами ентропії, використовуючи різні методи для їх очищення від неминучої передбачуваності. Однак на даний момент швидкість збору випадкових чисел усіма існуючими мікрочіпами (кілька тисяч біт в секунду) не відповідає швидкодії сучасних процесорів.
У сучасних дослідженнях здійснюються спроби використання вимірювання фізичних властивостей об'єктів (наприклад, температури) або навіть квантових флуктуацій вакууму в якості джерела ентропії для ГСЧ. [4]
Приклад найпростішого ГСЧ з джерелом ентропії
Якщо в якості джерела ентропії використовувати поточний час, то для отримання цілого числа від 0 до N досить обчислити залишок від ділення поточного часу в мілісекундах на число N +1. Недоліком цього ГСЧ є те, що протягом однієї мілісекунди він видає один і той же число.
Приклади ГСЧ і джерел ентропії
У цьому розділі не вистачає посилань на джерела інформації.
Генератор випадкових чисел для лотерей - апаратно-програмний комплекс, що застосовується в розіграшах, в яких необхідно вгадувати комбінацію з певної кількості чисел. Будь-яке з можливих чисел має однакову ймовірність появи.
Спроби створити генератор випадкових чисел відносяться до 3500 року до н. е. і пов'язані з давньоєгипетської настільною грою Сенет. У Сенет два гравці грають за дві сторони. Ходи визначаються за допомогою 4 плоских паличок, що і може вважатися генератором випадкових чисел того часу. Кидають всі чотири палички відразу. Підрахунок очок відбувається наступним чином: 1 паличка впала білої стороною вгору - 1 очко і додатковий кидок; 2 - 2 очка; 3 - 3 очка, 4 - 4 і додатковий кидок. Одна зі сторін палички чорна і якщо всі чотири палички падали чорної стороною вгору - це максимальний результат - 5 очок і додатковий кидок.
Відомий генератор випадкових чисел ERNIE застосовувався протягом багатьох років для визначення виграшних номерів британської лотереї.
Головні вимоги до ГСЧ, використовуваному для проведення розіграшів:
- Кожне число отримано випадково, не маючи нічого спільного з іншими числами в послідовності;
- Кожне число з цілого ряду має рівні шанси на випадання;
- Кожне число має задану ймовірність появи в будь-якої заданої області значень.
Найпоширеніший метод генерації випадкових чисел називається лінійний конгруентний метод. але є ще й інший - адитивний конгруентний метод. Ці методи генерують послідовність чисел, що задовольняє умові випадковості. Основою для використання цих та інших методів генерації випадкових чисел служить програмне забезпечення, нескінченно генерує числа, незалежно від того, знаходиться в даний час учасник в процесі гри чи ні. Завдяки цьому виключається можливість того, що гравець зможе самостійно визначити метод генерації, що використовується в даний момент, і «вгадати» випадають числа.
Наприклад, за законами США потрібно, щоб генератор випадкових чисел в ігрових автоматах функціонував весь час. Крім того, цим питанням займаються безпосередньо самі постачальники програмного забезпечення.
У російських державних лотереях ( «Гослото« 5 з 36 »,« Гослото «6 із 45», «Гослото« 7 з 49 »,« Спортлото 6 з 49 »,« Рапідо »,« Кено-Спортлото »,« Топ-3 »,« 12/24 »,« Все по сто ») для визначення переможців використовується генератор випадкових чисел - апаратно-програмний комплекс, сертифікований АНО МІЦ і відповідає рекомендаціям ФГУП ВНИИМС.
При використанні ГСЧ для розіграшів лотерей, слід дотримуватись таких вимог:
- Тестування потоку чисел на випадковість.
- Виняток можливостей втручання з метою підтасовування результатів розіграшу.
- Передача результатів розіграшу в центр обробки ставок в момент визначення виграшної комбінації з точністю до мілісекунди.
- Можливість резервування з автоматичним перемиканням на запасне обладнання в разі несправності.