Blum-Blum-Shub generator и его применение

В настоящее время случайные числа используются в различных областях науки. Например, для моделирования различных реальных процессов зачастую нужно учитывать не только поведение исследуемой величины, но и влияние различных непредсказуемых явлений. Кроме того, в некоторых методах анализа данных, полученных в результате эксперимента, также используются случайные числа. В теории игр случайность также играет большую роль. Ну и конечно в криптографии. Многие алгоритмы шифрования или электронной подписи используют случайные числа.

Но как же получить случайное число?  В природе существует много различных случайных явлений, на основе которых придумали генераторы. Аппаратные генераторы случайных чисел могут быть основаны на макроскопических случайных процессах с использованием таких предметов, как монетка, игральная кость или колесо рулетки. Но такие генераторы являются очень медленными и не подходят для решения задач. Для более быстрого получения случайных чисел могут использоваться физические явления, имеющие квантовую природу, например шум в электрических цепях. Но главным минусом аппаратных генераторов случайных чисел является их ненадежность, связанная с частыми сбоями в работе. Чтобы избежать ненадежности, стали использовать заранее полученные таблицы случайных чисел. Однако и они имели большой минус - занимали много памяти.

Так как ни аппаратный метод, ни таблицы случайных чисел не удовлетворяли потребность в быстром и надежном получении случайных чисел, ученые начали искать алгоритмические методы получения случайных чисел. Очевидно, что полученная в результате таких методов последовательность уже не является случайной, так как полностью определяется некоторой формулой и начальными данными. Но если начальное значение хранится в секрете, а алгоритм стойкий (стойким считается алгоритм, успешная атака на который требует от атакующего обладания недостижимым на практике объёмом вычислительных ресурсов), то результаты, которые выдает генератор будут непредсказуемыми. Такой алгоритм получения последовательности чисел, свойства которой аппроксимируют последовательность случайных чисел, называют генератором псевдослучайных чисел.

Источник: Хабрахабр