Лабораторна робота №1
Теоретичні відомості
Загальні відомості про псевдовипадкові послідовності
Випадкові числа застосовуються в широкому діапазоні математичних алгоритмів, які знаходять вжиток як в задачах чистого програмування, так і в статистичних методах, типу метода Монте-Карло. Для того щоб отримати такі послідовності, використовуються так звані генератори псевдовипадкових послідовностей.
Генератор псевдовипадкових чисел (ГПВЧ, англ. Pseudorandom number generator, PRNG) - алгоритм, що генерує послідовність чисел, елементи якої майже незалежні одне від одного й підкоряються заданому розподілу (зазвичай рівномірному).
Ці генератори звуться псевдовипадковими через те, що отримані в їх результатах послідовності все-таки містять в собі деякі закономірності. Американський математик Джордж Марсалія склав так звані статистичні тести DIEHARD, які перевіряють їх наявність у алгоритмі ГПВЧ. Серед них наступні:
Дні народження;
Перестановки, що перетинаються;
Ранги матриць;
Тест мавпи (при цьому викинута послідовність перетворюється на текст і аналізується відсутність семантично значущих послідовностей);
Підрахунок одиниць (викинуті послідовності перетворюються в бітову форму і підраховується кількість послідовних одиниць);
Тест гри в кості (імітується 200 000 підкидань кості).
За результатами цих, а також інших тестів, повинна бути отримана послідовність із розподілом по Пуассону чи за нормальним законом розподілу. Якщо послідовність такому закону не відповідає, тест вважається проваленим.
На сьогодні в програмуванні використовуються наступні алгоритми, які частково, або повністю проходять тести DIEHARD.
Лінійний конгруентний алгоритм (алгоритм Лемера)
Цей алгоритм полягає у обчисленні деякої рекурсивної послідовності по модулю. Формула надзвичайно проста:
a, c – деякі цілочисельні аргументи.
Отримана послідовність цілком залежить від обраного числа X0, і при різних його значеннях будуть отримані різні ряди. В той же час, чільна частина статистичних властивостей цих рядів залежить від значень аргументів a та c, і від стартового числа не залежать. Така двоїстість дозволяє генерувати статистично хороші послідовності, однак він не є криптостійким через наявність однозначної залежності від початкового числа.
Зазвичай цей алгоритм використовується для навчальних посібників, а також входить в набір стандартних функцій більшості мов програмування, оскільки допускає реалізації генератора ПВЧ як із будь-якою розрядністю.
При реалізації цього алгоритму часто обирають значення 2e, де e – число бітів в машинному слові. Це пришвидшує алгоритм, адже дозволяє позбавитись операції цілочисельного ділення, але в такому разі збільшується залежність від X0 і знижується криптостійкість.
Алгоритм Mother-of-All
Алгоритм «Всезагальна Матір» був запропонований Джорджем Марсалією як узагальнення конгруентного методу. Він базується на множенні із перенесенням і має період в 2250, на відміну від класичного алгоритму Лемера. Він позбавлений всіх його недоліків, однак він може бути реалізований виключно із 64-бітною розрядністю, через великий розмір коефіцієнтів. Це робить його погано застосовним для асемблерних програм, а також надто повільним, тому що для отримання псевдовипадкових послідовностей із малою кількістю цифр необхідно використовувати як початкові аргументи числа в діапазоні між 0 та 1.
, , S – наудачу взяте число, яке править за «seed», початкове число послідовності. На практиці через велику розрядність цього алгоритму, як xn, так і С на початковій ітерації встановлюють рівними і визначають як випадкове число, отримане за допомогою іншого генератора ПВЧ, або найчастіше – поточне значення таймера.
Алгоритм вихору (Mersenne Twister)
Алгоритм вихору Мерсенна був запропонований в 1997 р. Мацумото Макото та Нішімурою Такуджі. Заснований він на властивостей простих чисел Мерсенна і забезпечує швидку генерацію псевдовипадкових послідовностей.
Прості числа Мерсенна широко застосовуються в математичному програмуванні, бо вони засновані на ступені двійки. Загальна формула таких чисел:
, де n – натуральне число
Відповідно, найпростіша послідовність простих чисел виглядатиме наступним чином:
Тим не менш, цей алгоритм застосовний лише в обмеженому спектрі задач, так як не є криптостійким. Достатньо аналізу 624 елементів послідовності, і цього досить для визначення будь-якого іншого її елементу. Тим не менш, на сьогодні існує тільки один вид шифрувального алгоритму, заснований на вихрі Мерсенна – запропонований він все тим же Мацумото – однак із іншими криптографічними алгоритмами він виграє виключно за рахунок швидкості.
Як і попередній, цей алгоритм має високу розрядність. Для отримання масива 32-бітних чисел необхідні 64-бітні обчислення. У якості стартової точки також вибирається наугад взяте число, наприклад, поточне значення таймера. Далі числа послідовно множаться за модулем два і зсуваються два рази вправо і і два рази вліво на кількість бітів, що відповідають простим числам Мерсенна, і множаться на 16-бітні коефіцієнти. Процедура зсуву, власне, і створює той самий вихор. Так, наприклад, для 32-бітних чисел математично алгоритм буде виглядати наступним чином:
4022730752
В такий спосіб можна згенерувати послідовність 64-бітних чисел, з яких беруться молодші 32 біт. Аналогічним способом генеруються будь-які інші послідовності, також можуть змінюватись і прості числа, на які відбувається зсув. Якщо такі числа більші за 64, відбувається циклічний зсув.