Криптография и шифрование - Простейшие алгоритмы генерации

Криптография > Псевдослучайные последовательности > Простейшие алгоритмы генерации

Простейшие алгоритмы генерации

Заслуга конструирования длинных псевдослучайных рядов с хорошими статистическими свойствами полностью принадлежит криптографии. Не следует думать, что они нужны лишь криптографам - картирование Венеры стало возможным, когда длина периода случайного ряда импульсов превысила 10**40. Фотографирование этой планеты нельзя было сделать потому, что она всегда закрыта плотным слоем облаков. Локация же ее с Земли затруднена обилием помех и высокими требованиями к разрешению. Поэтому зондирование выполнялось случайной последовательностью импульсов указанного периода. После 300 зондирований, на что ушло более полгода, была получена карта, где различимы объекты размером около километра, а по высоте разрешение получено такое, какое достигнуто не везде на Земле. Генераторы псевдослучайных чисел используются очень широко в сотнях программных приложений от конструирования ядерных реакторов и радиолокационных систем раннего обнаружения до поисков нефти и многоканальной связи. Генерация псевдослучайных последовательностей давно занимала математиков. Одним из первых было предложение получать их как значения дробной части многочлена первой степени:

                Yn = Ent (a*n+b)

Если n пробегает значения натурального ряда чисел, то поведение Yn выглядит весьма хаотичным. Еще Карл Якоби доказал, что при рациональном коэффициенте а множество {Yn} конечно, а при иррациональном бесконечно и всюду плотно в интервале от 0 до 1. Для многочленов больших степеней такая задача была решена лишь в 1916 году выдающимся математиком нашего века Германом Вейлем. Кроме того, он установил критерий равномерности распределения любой функции от натурального ряда чисел. Небезынтересно привести его в краткой формулировке.

КРИТЕРИЙ ВЕЙЛЯ. Чтобы ряд х1, х2, x3, ... был распределен равномерно в интервале от 0 до 1, необходимо и достаточно, чтобы для любой интегрируемой по Риману функции f(x) было справедливо соотношение P{=Mf(x)}=1.

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

Однако эти результаты далеки от практики получения псевдослучайных рядов чисел. Дело в том, что теорема Якоби относится к действительным числам х и у, которые не могут быть использованы при вычислениях, потому что иррациональные действительные числа требуют для своей записи бесконечного числа знаков. Попытки замены настоящего иррационального числа его приближением на ЭВМ для генерации псевдослучайной последовательности опасны, так как получаемые последовательности оканчиваются циклами с коротким периодом. Завершают доказательство непригодности полиномиальных и других функциональных преобразований натурального ряда чисел для получения псевдослучайных последовательностей результаты Пуанкаре. В частности он установил, что непрерывное отображение Т области U числового пространства в себя обязательно приводит к короткой цикличности траекторий Tn(х) для всюду плотного в U множества точек, если учитывать попадание траекторий точек в их сколь угодно малые окрестности или ряды чисел, созданные таким методом, отягчены периодичностями.