Криптография и шифрование

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

Простые числа

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

     G(n+1)=KGn+C MOD M

В нем каждое последующее псевдослучайное число G(n+1) получается из предыдущего Gn умножением его на К, сложением с С и взятием остатка от деления на М. Весь фокус здесь в том, чтобы подобрать хорошие значения К, С и М, на что были потрачены десятилетия работы математиков. Подбор почти иррациональных К ничего не дает. Например, выбрав закон генерации последовательности G(N+1) = Ent (sqr(2)*Gn) на IBM PC при формате представления чисел с плавающей запятой IEEE в 4 байта, получим псевдослучайные ряды, обязательно заканчивающиеся циклами с периодами длиной всего лишь 1225 и 147 в зависимости от начального заполнения. Разумнее вычисления вести в целых числах. Для них было установлено, что при С=0 и М=2**N наибольший период М/4 достигается при K=3+8*i или K=5+8*i и нечетном начальном числе. При достаточно больших К ряд производит впечатление случайного. Насколько это верно читатель может выяснить самостоятельно следующей программой:

'----------проверка  случайности ряда чисел
DEFINT  A-Z: SCREEN  2: CLS
n =  1
DO
nold = n: n =  FnRnd% (n)
PSET (nold/64,CVL(MKI$(n)+MKI$(0) )\512)
LOOP UNTIL n =  1
END
'----генерация ряда чисел с периодом 16384
DEF FnRnd% (n) =CVI(LEFT$(MKL$(1381&*n) ,2))

В ней случайность ряда проверяется отображением на экране дисплея пар его чисел (Gn+1, Gn) в прямоугольнике размером 128 х 512. Это простой и удобный способ проверки случайности рядов чисел, так как на глаз заметны малейшие закономерности в получаемом орнаменте. Из опытов с этой программой можно убедиться, что как ни экспериментируй с подбором К, все равно закономерности видны и чисто случайного ряда чисел не получишь. Вспомните ехидное предложение Додо "становиться строго в беспорядке" из "Алисы в стране чудес". Результат можно несколько улучшить. Если С нечетно и K=1+4*i, то период ряда равен М. После долгих поисков К исследователи остановились на значениях 69069 и 71365. Кроме значений М=2**N широко используются выборы простых М, например, простого числа М=2**31-1, известного со времен Эйлера (Это число "плохо" тем, что в двоичной записи содержит лишь единицы. Однако оно может использоваться, если вычисления выполняются в десятичной арифметике.)