Генератор на случайни числа: Как компютрите генерират произволни числа?

Хората използват случайни числа от хилядолетия, така че концепцията не е нова. От лотарията в древния Вавилон, до масите за рулетка в Монте Карло, до игрите със зарове във Вегас, целта е крайният резултат да бъде оставен на случаен принцип.

Но хазартът настрана, случайността има много приложения в науката, статистиката, криптографията и др. И все пак използването на зарове, монети или подобни носители като произволно устройство има своите ограничения.

Поради механичния характер на тези техники, генерирането на големи количества случайни числа изисква много време и работа. Благодарение на човешката изобретателност, ние разполагаме с по-мощни инструменти и методи.

Методи за генериране на случайни числа

Истински случайни числа

електронен робот със свободна форма, оглеждащ се

Нека разгледаме два основни метода, използвани за генериране на случайни числа. В първия метод евъз основа на физически процес и събира източника на случайност от някакъв физически феномен, който се очаква да бъде случаен .

Подобно явление се случва извън компютъра. Измерва се и се коригира за възможни отклонения поради процеса на измерване. Примерите включват радиоактивен разпад, фотоелектричния ефект, космическо фоново излъчване, атмосферен шум (който ще използваме в тази статия) и др.

По този начин за случайни числа, генерирани въз основа на такава случайност, се казва, че са „ истински “ случайни числа.

Технически, хардуерната част се състои от устройство, което преобразува енергията от една форма в друга (например радиация в електрически сигнал), усилвател и аналогово-цифров преобразувател, за да превърне изхода в цифров номер.

Какво представляват псевдослучайните числа?

Хакерски двоичен код за атака.  Изработен с Canon 5d Mark III и аналогов ретро обектив, Leica APO Macro Elmarit-R 2.8 100mm (Година: 1993)

Като алтернатива на „истинските“ случайни числа, вторият метод за генериране на случайни числа включва изчислителни алгоритми, които могат да дадат очевидно случайни резултати.

Защо очевидно случайно? Тъй като крайните резултати, получени в действителност са напълно определени с начална стойност известен също като семена стойност или ключ . Следователно, ако знаете ключовата стойност и как работи алгоритъмът, можете да възпроизведете тези привидно случайни резултати.

Генераторите на случайни числа от този тип често се наричат генератори на псевдослучайни числа и в резултат на това извеждат псевдослучайни числа.

Въпреки че този тип генератор обикновено не събира никакви данни от източници на естествена случайност, такова събиране на ключове може да бъде възможно при необходимост.

Нека да сравним някои аспекти на истинските генератори на случайни числа или TRNG и генераторите на псевдослучайни числа или PRNG .

PRNG са по-бързи от TRNG. Поради детерминирания си характер, те са полезни, когато трябва да повторите последователност от случайни събития. Това помага много при тестването на код например.

От друга страна, TRNG не са периодични и работят по-добре в чувствителни към сигурността роли като криптиране.

А период е броя на повторенията на PRNG минава през, преди да започне да се повтаря. По този начин, при равни други условия, 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 алгоритми.

Що се отнася до алгоритмите за генератор на произволни числа, които могат да се изпълнят от компютри, те датират още през 40-те и 50-те години (методът на средния квадрат и генератор на Лемер например) и продължават да се пишат днес (Xoroshiro128 +, Squares RNG и др.) .

Примерен генератор на случайни числа

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

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

Но самата тази статия е за генериране на случайни числа. Затова реших да се науча как да събирам "истински" данни, базирани на случайност, и да споделя откритието си с вас.

Така по-долу е "истинският" генератор на случайни числа. Задайте параметрите и натиснете Generate.

Истински генератор на случайни числа двоичен десетичен шестнадесетичен генерира резултат:

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