Псевдовипадкові послідовності (числа) — послідовності, що отримуються за цілком невипадковим алгоритмом, але мають властивості, дуже подібні до властивостей реалізацій випадкових чисел.

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

Історія Перші спроби отримання випадкових чисел за допомогою комп'ютерів розпочалися в середині XX століття. У 1946 році Джон фон Нейман запропонував метод середніх квадратів. Ідея полягала в тому, щоб взяти число, піднести його до квадрата і взяти середні цифри результату як наступне число. Хоча метод був простим, він виявився ненадійним: послідовності швидко зациклювалися або збігалися до нуля.

У 1951 році Деррік Генрі Лесмер винайшов лінійний конгруентний метод, який став основою для більшості генераторів псевдовипадкових чисел на наступні півстоліття. З розвитком криптографії та методів імітаційного моделювання (Монте-Карло) вимоги до якості генераторів зросли, що призвело до створення складніших алгоритмів, таких як Вихор Мерсенна (1997) та сімейство Xorshift (2003).

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

Зазвичай генерування псевдовипадкової послідовності передбачає два етапиБахрушин В. Є. Математичні основи моделювання систем: Навчальний посібник для студентів. — Запоріжжя, 2008. — 294 с.Бусленко Н. П. Моделирование сложных систем. — М. : Наука, 1968.. На першому генерують псевдовипадкові числа, що мають рівномірний розподіл на відрізку від нуля до одиниці. На другому цю послідовність перетворюють у послідовність, що має заданий закон розподілу.

Базові характеристики

Період Оскільки будь-який програмний алгоритм оперує скінченним обсягом пам'яті, послідовність станів генератора неминуче почне повторюватися. Періодом називається мінімальна довжина послідовності, після якої вона повністю відтворює сама себе.

Початкове значення Псевдовипадкова послідовність є повністю детермінованою. Вона залежить від початкового стану генератора, який називають зерном (англ. seed). Якщо ініціалізувати генератор тим самим зерном, він видасть ідентичну послідовність чисел. Ця властивість корисна для налагодження програм та відтворюваності наукових експериментів, але є вразливістю в кібербезпеці.

Відтворюваність: Якщо ініціалізувати генератор тим самим зерном, він видасть ідентичну послідовність чисел. Це критично важливо для налагодження програмного забезпечення та верифікації наукових експериментів. Ініціалізація: Для отримання різної послідовності при кожному запуску програми як зерно часто використовують поточний системний час або дані з апаратних джерел ентропії.

Рівномірність розподілу Більшість базових генераторів видають числа, рівномірно розподілені на інтервалі [0, 1). Статистична якість перевіряється через дискрепансію — міру відхилення розподілу точок послідовності від ідеального рівномірного розподілу.

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

Існує ряд методів, які відповідають критеріям перевірки «випадковості» побудови таких чисел з розподілом близьким до рівномірного (хоча ці числа взаємозалежні).

Зазвичай використовують деяке рекурентне співвідношення. Це значить, що кожне наступне число αk+1 утворюють із попереднього αk (або групи попередніх чисел), використовуючи деякий алгоритм, який використовує арифметичні та логічні операції.

Часто застосовується метод остач, який належить до так званих аналітичних методів і полягає в побудові послідовності {αn} згідно із рекурентним співвідношенням αn+1 = Kαn (mod M), де К та M — деякі константи.

Для генерування псевдовипадкових чисел, що мають рівномірний розподіл на відрізку від нуля до одиниці використовують методи: метод остач (лінійний конгруентний метод); метод середніх квадратів (метод фон Неймана); метод трикутного відображення; метод логістичного відображення.

Перетворення в послідовність з заданим розподілом

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

Обов'язковим етапом генерування псевдовипадкових чисел є перевірка періодичності й випадковості отриманої послідовності та її відповідності заданому закону розподілу.

Квазівипадкові послідовності Окремим класом послідовностей, які часто розглядаються в контексті псевдовипадкових чисел, є квазівипадкові послідовності (або послідовності з низькою дискрепансією).

На відміну від звичайних псевдовипадкових чисел, які намагаються імітувати повну незалежність значень, квазівипадкові послідовності розроблені так, щоб заповнювати простір максимально рівномірно, уникаючи скупчень (кластеризації) та прогалин. Це робить їх ефективнішими за звичайні випадкові числа в чисельних методах інтегрування (Квазі-Монте-Карло).

Відомі приклади квазівипадкових послідовностей:

Послідовність Соболя: використовує операції в полі Галуа для рівномірного покриття n-вимірного гіперкуба. Послідовність Галтона: узагальнення одновимірної послідовності ван дер Корпута на багатовимірний простір за допомогою простих чисел. Послідовність Фора

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

ISO/IEC 18031: Міжнародний стандарт, що визначає принципи генерації випадкових бітів для криптографічних цілей. NIST SP 800-90A: Серія рекомендацій Національного інституту стандартів і технологій США, що описує затверджені алгоритми (Hash_DRBG, HMAC_DRBG, CTR_DRBG). Варто зазначити, що один із алгоритмів цього стандарту, Dual_EC_DRBG, був вилучений через підозру у наявності прихованої вразливості. ДСТУ 4145-2002: Український стандарт цифрового підпису, який також висуває вимоги до генерації випадкових чисел при створенні ключів.

Застосування

Метод Монте-Карло Псевдовипадкові послідовності є основою стохастичного моделювання (метод Монте-Карло). Цей метод використовується для наближеного обчислення інтегралів, розв'язання диференціальних рівнянь, моделювання перенесення частинок у ядерній фізиці та оцінки фінансових ризиків. Для цих задач критично важливою є відсутність кореляції між числами (щоб уникнути систематичної похибки).

Комп'ютерна графіка та ігри У відеоіграх ПВП використовують для створення ілюзії непередбачуваності: поведінка ворогів, генерація предметів, розрахунок пошкоджень. Також псевдовипадковість лежить в основі процедурної генерації контенту (ландшафтів, текстур, рівнів). Використання фіксованого зерна (seed) дозволяє генерувати нескінченні, але повторювані світи (як у грі Minecraft або No Man's Sky), не зберігаючи їх повністю на диску.

Телекомунікації У системах зв'язку з розширеним спектром, таких як GPS, CDMA, Wi-Fi, використовуються псевдовипадкові коди (наприклад, коди Голда або послідовності M-послідовності). Вони дозволяють модулювати сигнал так, що він виглядає як шум для стороннього спостерігача, забезпечують завадостійкість та дозволяють багатьом абонентам одночасно використовувати одну частоту.

Дивись також

Генератор псевдовипадкових чисел Список криптографічних алгоритмів

Примітки

Джерела та література