Кpиптогpафия от папиpуса до компьютеpа


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


Несмотря на непригодность для криптографии простых последовательностей чисел, рассмотрим все же самые распространенные из них. Наиболее древний вычислительный способ генерации псевдослучайных чисел на ЭВМ принадлежит Джону фон Нейману и относится к 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))




- Начало -  - Назад -  - Вперед -



Книжный магазин