Методи генерування випадкових чисел з рівномірним законом розподілу

Введення

Промисловість не стоїть на місці. Ще у 1990 році псевдовипадкові числа, довжиною в цілих 40 біт, згенеровані на ЕОМ можна було вгадати за кілька годин [1]. На сьогоднішній же день, якісні характеристики випадкових величин на ЕОМ вражає навіть досвідчених математиків. У багатьох областях застосування алгоритмів генерацій всевдослучайных чисел існує ряд обмежень, пов'язаних з тим чи іншим недоліком методів їх генерації. Вдосконалення існуючих методів сприяє високий інтерес до теми, який підвищується з ростом числа публікацій. Нехай ця стаття стане моїм внеском у розвиток методів моделювання та генерації випадкових процесів, так важливих для моїх досліджень і розробок.

Передісторія
ДжерелоЯк працює новий генератор випадкових чисел Intel

Короткий екскурс в історію методів генерації випадкових чисел показує, що в гонитві за стохастичностью розробники готові були йти на крайні заходи. Так в 1996 році був винайдений і запущений джерело випадкових чисел під назвою Lavarand. Метод генерації чисел був зведений до обробки фотографії декоративного світильника – лавової лампи, яка безперервно змінювала свій вигляд непередбачуваним чином [2]. Також варто згадати і про перше генераторах випадкових величин на звичайних ЕОМ. Розробила їх фірма Intel в 1999 році, і називався цей компонент Firmware Hub. Метод генерації полягав у реєстрації теплового шуму резисторів з подальшим посиленням і використанням в якості керуючого сигналу осцилятора, регулярно змінює своє між значенням «0» і «1» [3].Така система працювала безперервно, незалежно від потреби користувача у використанні системи генерації випадкових чисел.
Головна проблема генерації істинно випадкових чисел залишається обов'язкова наявність аналогової складової, так як якісні характеристики цифрових методів генерації псевдовипадкових чисел не задовольняють багатьом стандартам National Institute of Standards and Technology, а на практиці абсолютно не годяться для вирішення багатьох завдань прикладного характеру, наприклад криптографії.



Рис.1 Схема генератора випадкових чисел.

У квітні 2012 року в продаж надійшли перші процесори з мікроархітектурою під кодовою назвою «Ivy Bridge». Особливістю цієї архітектури стала наявність генератора, що дозволяє використовувати аналогові теплові шуми безпосередньо для генерації випадкових чисел [4]. На рис.1 представлена схема такого генератора. На перший погляд вона надто ідеалізована, адже рівноймовірного появи «0» або «1» можна досягти тільки за абсолютної ідентичності інверторів, чого на практиці домогтися неможливо. Тому нерівномірність генеруються чисел потрібно компенсувати, що і робиться в постобробці.

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

Мабуть, найбільш важливими і незамінними методами моделювання випадкових процесів, є методи генерації рівноймовірно випадкових величин, так як більша частина алгоритмів моделювання випадкових процесів з довільним законом розподілу базуються саме на них [5].
Найпопулярнішими способами отримання рівномірно розподілених випадкових величин є:
• Таблиці випадкових чисел
• Фізичні генератори випадкових чисел (такі як Firmware Hub або генератор випадкових чисел " Ivy Bridge ")
• З допомогою цифрових генераторів або датчиків, з використанням формул.
Треба сказати, що в останньому пункті результатом генерації є псевдовипадкові числа. Як би не парадоксально звучало таке твердження, але головним недоліком таких чисел – це те, що в більшості випадків їх неважко передбачити, а в деяких алгоритмах генерації їх послідовність ще й має властивість періодично повторюватися. У деяких прикладних задачах це неприпустимо, але, незважаючи на це, саме ці способи генерації випадкових величин з рівномірним законом розподілу одержали найбільше поширення, через простоти їх реалізації на ЦЭВМ.
Серед них найбільш популярними вважають:
• Конгруентні методи.
• Методи, засновані на використанні регістра зсуву з лінійним зворотним зв'язком (LFSR).
Лінійний конгруэнтный метод донині використовується для генерації випадкових чисел в самих популярних середовищ програмування, таких як MSVS [6], MSVB [7], Java [6], Borland C/C++ [6], GCC [8] та інших. Поширеність цього методу говорить про його ефективність.
Суть методів цього класу полягає в обчисленні послідовності випадкових чисел Y(n):
Y(n+1) = (x*Y(n) + c) % m,
де m – кількість значень з яких формується послідовність (m ≥ 2), % — залишок від ділення, x – множник (0 ≤ x < m), с – приріст (0 ≤ < m), Y(0) – початкове значення (0 ≤ Y(0) < m) [9].
Від вибору чисел m, x, c, Y(0) залежать якісні параметри стохастичності отриманих чисел.
Мабуть, самим універсальним у використанні, є клас методів, що використовують зсувні регістри. Вони незамінні, як в задачах криптографії [10] (GSM, Bluetooth) так і тестування цифрових пристроїв [11]. Є згадки використання одного з таких алгоритмів в якості подільника тактової частоти або лічильника [12]. Також алгоритми з використанням сдвигового регістра використовуються в задачах скремблювання [13].



Рис.2 Схема регістра зсуву зі зворотнім зв'язком

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

Висновок

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

Список використаних джерел:

[1] Goldberg, I. Randomness and the Netscape Browser / I. Goldberg, D. Wagner // Dr. Dobb's Journal. – 1996. – January, P. 66-70.
[2] Патент US № 7031991 B2 Hadamard-transform on-line randomness test / Laszlo Hars 17 apr. 2002.
[3] Jun, B. The Intel Random Number Generator / B. Jun, P. Kocher // Cryptography Research Inc. white paper, 1999.
[4] Як працює новий генератор випадкових чисел Intel
[5] Монаков, А. А. Основи математичного моделювання радіотехнічних систем: навч. посібник / А. А. Монаков; ДУАП. СПб., 2005. 15 с.
[6] ISO/IEC 9899:201x Last public Committee Draft from April 12, 2011, page 346f.
[7] Як Visual Basic Generates Pseudo-Random Numbers for the RND Function. Microsoft Support. Microsoft
[8] GNU Scientific Library: Other random number generators
[9] Дональд Кнут. Том 2. Получисленные методи // Мистецтво програмування. Указ. соч. — С. 21-37.
[10] Barklan E., Biham E., Keller N. Instant ciphertext-only криптоаналіз of GSM encrypted communication. — Journal of cryptology №21-3, 2008.
[11] Ларін, А. Л. Основи цифрової електроніки: навчальний посібник / А. Л. Ларін; М.: МФТІ, 2008. — 314 с. — ISBN 978-5-7417-0228-4.
[12] Efficient Shift Registers, LFSR Counters and Long Pseudo-Random Sequence Generators
[13] Варгаузин, Ст. Принципи цифрового телебачення стандарту ATSC / В. Варгаузин — Журнал Теле-Супутник №9(47), 1999.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.