Случайные и псевдослучайные числа
Генерация псевдослучайных чисел – это создание произвольной числовой последовательности с помощью заданного детерминированного алгоритма, элементы которой хотя и подчиняются некоторому распределению, но, тем не менее, в большинстве ситуаций могут быть использованы в качестве случайных.
Наличие класса псевдослучайных чисел связано с тем, что программно создаваемые генераторы случайных чисел устроены так, что при их многократном вызове рано или поздно будет начинать прослеживаться некоторая закономерность в появлении каждого последующего случайного числа (что вызвано зацикливаемостью алгоритмов и зачастую предсказуемостью используемых в них формул для генерации этих чисел). Поэтому истинно случайными они уже не будут являться, и их называют псевдослучайными числами.
В целом назначение этих чисел такое же, как и у случайных чисел (последовательности которых невозможно предугадать и вообще повторно воспроизвести), поэтому по своим свойствам псевдослучайные числа должны быть максимально приближены к истинно случайным числам и иметь схожие с ними статистические свойства.
В алгоритмах генерации псевдослучайных чисел принято использовать некое случайное начальное значение – seed («зерно»), от которого по специальной формуле начинает вычисляться вся последовательность, в то время как для создания последовательности истинно случайных чисел такое «зерно» (то есть входные данные алгоритма) каждый раз заново производится с помощью аппаратных генераторов или программно-аппаратными средствами, такими как различные устройства компьютера. Например, в качестве источников при создании случайной последовательности чисел можно использовать шумы центрального процессора, различные движения компьютерной мыши, интервалы по времени между нажатиями клавиш и, в особенности, системное время. Но скорость получения таких последовательностей обычно бывает медленной, тем более при генерации достаточно больших по объёму последовательностей.
Поэтому на практике обыкновенно используются именно псевдослучайные числа. Но выбор во многом зависит от специфики решаемой задачи. В частности, в задачах из области web-безопасности, связанных с шифрованием и созданием паролей, целесообразнее использовать истинно случайные числа. Тем не менее, при моделировании виртуальной реальности и создании в компьютерных играх эффекта непредсказуемости, а также при решении многих задач криптографии будет удобнее работать именно с псевдослучайными числами.
Особенности генераторов псевдослучайных чисел
Итак, поскольку вычислительные ресурсы компьютеров ограничены, а генераторы истинно случайных чисел очень ресурсозатратны, то естественным образом возникла необходимость по разработке генераторов последовательностей псевдослучайных чисел.
Принцип их программной реализации такой, что в отличие от генераторов истинно случайных чисел они всегда обладают некоторой периодичностью, что связано с конечностью возможных состояний компьютерной вычислительной системы. Это означает, что при такой генерации через какое-то время обязательно возникнет некоторая повторяемость, и в получаемой последовательности произвольных чисел начнут проявляться заметные закономерности.
Поэтому, чтобы эффективно применять в различных практических задачах псевдослучайные числа, необходимо использовать такой алгоритм, при котором период повторяемости будет достаточно большим.
В представленной далее таблице можно посмотреть на различия в характеристиках истинно случайных и псевдослучайных чисел:
Рисунок 1. Таблица. Автор24 — интернет-биржа студенческих работ
Любой генератор псевдослучайных чисел включает в себя следующие структурные компоненты:
- Источник энтропии – то, что привносит в алгоритм элемент непредсказуемости и неопределённости, то есть это источник хаоса и беспорядочности.
- Блок для хранения внутреннего состояния генератора.
- Блок для создания очередного произвольного значения.
- Блок, осуществляющий переход алгоритма на следующий шаг.
Далее перечислены основные признаки, по которым можно классифицировать генераторы псевдослучайных чисел:
- тип используемого нелинейного преобразования, которое может быть квадратичным, кубическим и т. д.;
- структура генератора последовательностей псевдослучайных чисел;
- наличие внешних источников энтропии.
Более подробно всевозможные виды генераторов псевдослучайных последовательностей представлены на следующем рисунке:
Рисунок 2. Виды генераторов псевдослучайных последовательностей. Автор24 — интернет-биржа студенческих работ
Важным является понятие стойкости выбранного нелинейного преобразования ко взлому. Наиболее широкое применение получили криптографически стойкие генераторы, которые создавались на основе специальных криптоалгоритмов, предполагающих использование различных блочных и поточных шифров, а также хэш-функций. Созданные на основе хэш-функций генераторы имеют достаточно обоснованную непредсказуемость, опираясь на такие вычислительные задачи, как разложение больших чисел на простые множители или дискретное логарифмирование.
Классификация генераторов псевдослучайных чисел
В настоящее время существует огромное разнообразие генераторов псевдослучайных чисел, среди которых наиболее популярными являются:
- линейные и нелинейные конгруэнтные генераторы;
- генераторы, основанные на регистрах сдвига с линейной обратной связью;
- генераторы, создаваемые с помощью нечёткой логики;
- аддитивные генераторы с запаздываниями на основе последовательностей, составленных из чисел Фибоначчи;
- «вихрь Мерсенна» – высокопроизводительный генератор, который использует свойства простых чисел.
