Алгоритми псевдовипадкових чисел
Більшість алгоритмів PRNG виробляють послідовності, які рівномірно розподілені будь-яким з декількох тестів. Це відкрите питання. Він один з центральних в теорії і практиці криптографії: чи є спосіб відрізнити вихід високоякісного PRNG від дійсно випадкової послідовності? У цій настройці розпізнавач знає, що використовувався відомий алгоритм PRNG (але не стан, з яким він був ініціалізований), або застосовувався дійсно випадковий алгоритм. Він повинен розрізняти їх.
Безпека більшості криптографічних алгоритмів та протоколів, що використовують PRNG, заснована на припущенні, що неможливо відрізнити застосування відповідного PRNG від використання дійсно випадкової послідовності. Найпростішими прикладами цієї залежності є потокові шифри, які найчастіше працюють, виключаючи або відправляючи відкритий текст повідомлення з виходом PRNG, створюючи зашифрований текст. Розробка криптографічно адекватних PRNG надзвичайно складна, оскільки вони повинні відповідати додатковим критеріям. Розмір його періоду є важливим чинником криптографічного придатності PRNG, але не єдиним.
Ранній комп’ютерний PRNG, запропонований Джоном фон Нейманом в 1946 році, відомий як метод середніх квадратів. Алгоритм наступний: візьміть будь-яке число, зведіть його в квадрат, видалите середні цифри отриманого числа як «випадкове число», потім введіть це число в якості початкового для наступної ітерації. Наприклад, зведення в квадрат числа 1111 дає 1234321, яке можна записати як 01234321, 8-значне число є квадратом 4-значного. Це дає 2343 як «випадкове число. Результат повторення цієї процедури — 4896 і так далі. Фон Нейман використовував 10-значні числа, але процес був таким же.
