Генератор випадкових чисел: як комп’ютери генерують випадкові числа?

Люди використовують випадкові числа протягом тисячоліть, тому концепція не нова. Починаючи з лотереї в стародавньому Вавилоні, закінчуючи столами для рулетки в Монте-Карло і закінчуючи іграми в кості у Вегасі, метою є залишити кінцевий результат на випадкові випадки.

Але азартні ігри вбік, випадковість має багато застосувань у науці, статистиці, криптографії та ін. Однак використання кубиків, монет або подібних носіїв як випадкового пристрою має свої обмеження.

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

Методи генерації випадкових чисел

Справжні випадкові числа

робот електроніки вільної форми озираючись

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

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

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

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

Що таке псевдовипадкові числа?

Двійковий код атаки хакера.  Зроблено з Canon 5d Mark III та аналоговим старовинним об'єктивом, Leica APO Macro Elmarit-R 2,8 100 мм (Рік: 1993)

Як альтернатива "справжнім" випадковим числам, другий спосіб генерації випадкових чисел включає обчислювальні алгоритми, які можуть давати очевидно випадкові результати.

Чому, мабуть, випадково? Оскільки отримані кінцеві результати насправді повністю визначаються початковою величиною, також відомою як початкове значення або ключ . Отже, якби ви знали значення ключа і як працює алгоритм, ви могли б відтворити ці, здавалося б, випадкові результати.

Генератори випадкових чисел цього типу часто називають генераторами псевдовипадкових чисел і, як результат, виводять псевдовипадкові числа.

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

Давайте порівняємо деякі аспекти справжніх генераторів випадкових чисел або TRNG і генераторів псевдовипадкових чисел або PRNG .

PRNG швидші, ніж TRNG. Через свою детермінованість вони корисні, коли вам потрібно відтворити послідовність випадкових подій. Наприклад, це дуже допомагає у тестуванні коду.

З іншого боку, TRNG не є періодичними і працюють краще в таких ролях, що відповідають рівням безпеки, таким як шифрування.

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

Приклад алгоритму генератора псевдовипадкових чисел

Комп’ютер виконує код, який базується на наборі правил, яких слід дотримуватися. Для PRNG загалом ці правила обертаються навколо наступного:

  1. Прийміть деякий початковий номер введення, тобто насіння або ключ.
  2. Застосовуйте це насіння в послідовності математичних операцій, щоб отримати результат. Цей результат є випадковим числом.
  3. Використовуйте отримане випадкове число як насіння для наступної ітерації.
  4. Повторіть процес, щоб імітувати випадковість.

Тепер розглянемо приклад.

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

Цей генератор видає ряд псевдовипадкових чисел. Враховуючи початковий початковий рівень X 0 і цілі параметри a як множник, b як приріст і m як модуль, генератор визначається лінійним відношенням: X n ≡ (aX n-1 + b) mod m . Або використовуючи більш зручний для програмування синтаксис: X n = (a * X n-1 + b)% m .

Кожен із цих членів повинен відповідати наступним умовам:

  • m> 0 (модуль додатний),
  • 0 <a <m (множник додатний, але менший за модуль),
  • 0b <m (приріст невід'ємний, але менший за модуль), і
  • 0X 0 <m (насіння невід’ємне, але менше модуля).

Давайте створимо функцію JavaScript, яка приймає початкові значення як аргументи і повертає масив випадкових чисел заданої довжини:

 // x0=seed; a=multiplier; b=increment; m=modulus; n=desired array length; const linearRandomGenerator = (x0, a, b, m, n) => { const results = [] for (let i = 0; i < n; i++) { x0 = (a * x0 + b) % m results.push(x0) } return results } 

Лінійний конгруентний генератор - один із найдавніших і найвідоміших алгоритмів PRNG.

Що стосується алгоритмів генератора випадкових чисел, які виконуються комп’ютерами, вони датуються ще 1940-х і 50-х років (наприклад, метод Середнього квадрата та генератор Лемера) і продовжують писатися сьогодні (Xoroshiro128 +, Squares RNG та багато іншого) .

Зразок генератора випадкових чисел

Коли я вирішив написати цю статтю про вбудовування генератора випадкових чисел у веб-сторінку, мені довелося зробити вибір.

Я міг використати Math.random()функцію JavaScript як основу та генерувати вихідні дані у псевдовипадкових числах, як це було в попередніх статтях (див. Таблицю множення - Таблиця власних часів)

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

Отже, нижче наведено "справжній" генератор випадкових чисел. Встановіть параметри та натисніть «Створити».

Справжній генератор випадкових чисел двійковий десятковий шістнадцятковий результат генерації:

The code fetches data from one of the APIs, courtesy of Random.org. This online resource has a plethora of useful, customizable tools and comes with excellent documentation to go with it.

The randomness comes from atmospheric noise. I was able to use asynchronous functions. That is a huge benefit going forward. The core function looks like this:

 // Generates a random number within user indicated interval const getRandom = async (min, max, base) => { const response = await  fetch("//www.random.org/integers/?num=1&min="+min+" &max="+max+"&col=1&base="+base+"&format=plain&rnd=new") return response.text() }

The parameters it takes allow a user to customize random number output. For example, min and max allow you to set lower and upper limits on generated output. And base determines if the output is printed as binary, decimal or hexadecimal.

Again, I chose this configuration but there are many more available at the source.

Коли ви натискаєте кнопку «Створити», handleGenerate()функція викликається. Він у свою чергу викликає getRandom()асинхронну функцію, управляє обробкою помилок і видає результати:

 // Output handling const handleGenerate = () => { handleActive(generateButton) const base = binary.checked ? 2 : decimal.checked ? 10 : 16 if (!minimum.value || !maximum.value) { prompter.style.color = 'red' prompter.textContent = "Enter Min & Max values" } else { getRandom(minimum.value, maximum.value, base).then((data) => { resultValue.textContent = data prompter.textContent = "" }).catch((error) => { resultValue.textContent = 'ERROR' prompter.textContent = 'Connection error. Unable to generate'; }) handleRestart() } } 

Решта коду стосується структури HTML, зовнішнього вигляду та стилю.

Код готовий до вбудовування та використання на цій веб-сторінці. Я розділив його на складові частини та надав детальні коментарі. Його легко можна змінити. Ви також можете змінювати функціональність та стилі відповідно до ваших потреб.

Це посилання на репозиторій GitHub повного коду: //github.com/sandroarobeli/random-generator