Разработка и исследование высокоскоростных генераторов псевдослучайных равномерно распределенных двоичных последовательностей (1025663), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

Также, несмотря на то, чтодля вычисления рекурренты (1.2) необходимо использовать 4д-разряднуюарифметику, период генератора ограничен сверху значением Ттах ^ 22q.Фон Нейман знал о проблемах, связанных с методом «середины квад­рата». Тем не менее, метод обладал достаточно высоким быстродействиемдля реализации на ENIAC, а «ошибки» генератора легко обнаруживалисьобслуживающим персоналом.1.2.4.2. М Е Т О Д У М Н О Ж Е Н И Я С П Е Р Е Н О С О МГенераторы, использующие метод умножения с переносом (см. [12]),основываются на рекуррентной зависимостиat+i = (а • at + ct) mod JV,t = 0,1,....(1.3)Параметрами генератора являются множитель а и модуль N, а началь­ное состояние определяется парой (ао, со)- В отличие от линейного конгру­энтного метода, в котором приращение с является константой, значениевеличины Ct зависит от членов последовательности ао, ct\,..., cxt-ict = (a- at-i + Cf_i) mod'iV.Следует отметить, что выходная последовательность а также можетбыть получена и при помощи мультипликативного конгруэнтного генера­тора с рекуррентным соотношениемPt+1 =(a-/3t)mod{aN-l),где каждый член (3 взят по модулю N, т.

е. at = f3t mod N (см. [52]).Период псевдослучайной последовательности, получаемой при помо­щи соотношения (1.3), зависит от значений ао и со и равен порядку эле--34мента N в мультипликативной группе по модулю aN — 1, т.е. в группе^алг-i чисел, взаимно простых с aN — 1 (см. [50,51]). Таким образом, мак­симально возможный период последовательности, полученной при помощиметода умножения с переносом, составляет Ттах — aN — 2.На практике для упрощения программной реализации обычно исполь­зуется модуль N = 2 9 , где q выбирается исходя из разрядности машинногослова [52]. В таком случае для представления чисел at, a, ct используется qбит, для вычисления выражения xt = (a-at + ct) — 2q бит, причем значениеat+\ соответствует q младшими битами числа Xt, a Ct+i — q старшим битам(т.е.

переносу — отсюда и происходит название алгоритма). Множитель авыбирается таким образом, чтобы числа aN — 1 и \aN — 1 были простыми.Если (ао,со) & {(0,0), (а — 1, N — 1)}, то выходная последовательность,вырабатываемая генератором, имеет период Т = \aN — 1.В [51] отмечается, что генератор обладает хорошими статистическимисвойствами и при q = 32 генератор успешно проходит все тесты из набо­ра DIEHARD. Тем не менее, в [19] сообщается о небольших отклоненияхстарших битов членов выходной последовательности от равномерного рас­пределения.1.2.4.3.

К В А Д Р А Т И Ч Н Ы Й К О Н Г Р У Э Н Т Н Ы Й М Е Т О ДДля вычисления членов последовательности в квадратичном конгру­энтном методе используется рекуррентная зависимость видаat+i = (а • al + 6 • o?f + с) modiV,t = 0,1,(1.4)Максимальный период квадратичного конгруэнтного генератора со­ставляет Tmax = N и достигается в том случае, когда одновременно выпол­нены следующие условия (см. [6,12]):- числа с и N взаимно просты;- числа а и Ь— 1 кратны р, где р — любой нечетный простой делитель 7V;- а четно, причем а = Ь— 1 (mod 4) при JV кратном 4 и а — Ь— 1 (mod 2)при N кратном 2;- если N кратно 9, то либо a (mod 9) = 0, либо a (mod 9) = 1 иас (mod 9) = 6.-35Особую значимость с точки зрения построения высокоэффективныхреализаций квадратичных конгруэнтных генераторов представляет случайN — 29, где q ^ 2 — число двоичных разрядов, используемых в ЭВМ дляпредставления целых (или беззнаковых) чисел.

При таком выборе модуляN максимальный период генератора составляет Ттах = 2я и достигается втом и только том случае, когда а четно, с нечетно, a b — нечетное число,удовлетворяющее соотношению Ъ = (а + 1) mod 4.Интересный вариант квадратичных конгруэнтных генераторов пред­ложил Роберт Ковэю (см. [6]):at+l= {at (at + 1)) mod2q,4 = 0,1,....Рекуррентное соотношение Ковэю получается из (1.4) подстановкой значе­ний параметров а = 1, Ъ — 1, с = 0, N — 2q (q ^ 2), а эффективность еговычисления практически не уступает линейному рекуррентному соотно­шению (1.1). Начальное значение CXQ выбирается таким образом, чтобы вы­полнялось равенство а$ (mod 4) = 2, при этом достигается максимальныйпериод выходной последовательности Ттах — 2д~2 = ^ . Тем не менее, сто­ит отметить, что для 32-разрядных ЭВМ при операциях над беззнаковымичислами q = 32 максимальный период составляет всего Ттах = 2 3 0 « 10 9членов.Еще один квадратичный конгруэнтный генератор был разработан в1986 г.

Ленор Блюм, Мануэлем Блюм и Майклом Шубом [16]. ГенераторБлюм-Блюм-Шуба (Blum-Blum-Shub, BBS) описывается рекуррентным со­отношениемat+i = о% mod TV,где модуль N является произведением двух достаточно больших простыхчисел Блюма: N = р\-р2 {р\,Р2 £ Р). Ч и с л а м и р2 должны быть сравнимыс 3 по модулю 4 (pi = 3mod4, р2 — 3mod4): это гарантирует, что каж­дый квадратичный вычет имеет единственный квадратный корень, такжеявляющийся квадратичным вычетом. Кроме того, наибольший общий де­литель GCD(</?(pi — 1), ip(j)2 — 1)) должен быть мал, что увеличивает длинупериода.-36-При правильном выборе параметров выходная последовательностьBBS-генератора статистически неотличима от истинно случайной [16,44].Несмотря на то, что генератор Блюм-Блюм-Шуба обладает очень хоро­шими статистическими свойствами, он не пригоден для использования взадачах моделирования из-за низкого быстродействия программной реа­лизации [44].

Тем не менее, BBS-генератор успешно используется в крип­тографии.1.2.4.4. И Н В Е Р С И В Н Ы Й ( О Б Р А Т Н Ы Й ) К О Н Г Р У Э Н Т Н Ы Й М Е Т О ДЧленыпоследовательности,вырабатываемойинверсивнымратным) конгруэнтным генератором (inversive congruential(об­generator,ICG) [22], описываются соотношениемat+i = (а- • &tl + с) mod p.В качестве модуля обычно используется простое число р G Р. Таким обра­зом, все вычисления выполняются в поле F p . Поскольку нулевой элементполя F p не имеет обратного по умножению [7], операция сГх определяетсяследующим образом для всехр е IP и a G F p :О,aа = 0,-1modp,а Ф 0.Максимальный период инверсивного конгруэнтного генератора по мо­дулю простого числа р равен | F p | = р и достигается в том и только томслучае, когда многочлен х2 — сх — а является примитивным над F p [22].На инверсивном конгруэнтном методе основаны явные инверсивныеконгруэнтные генераторы (explicit inversive congruential generator, EICG),описываемые соотношениемat+i = (a(t + to) + c)~ mod p.Параметр с в соотношении является избыточным: легко показать, что гене­раторы с параметрами (р, а, с, ц ) и (р, а, 0, ц ) вырабатывают одинаковые,(2).(1),_11последовательности при ц ' — ц ' + а с.-37яТакже используются генераторы, построенные по модулю 2 , где q €N.

Более подробно инверсивные конгруэнтные генераторы и их свойстварассмотрены в [18,21-23,62].Основным достоинством инверсивных конгруэнтных генераторов яв­ляются их хорошие статистические свойства. Тем не менее, они значитель­но проигрывают по быстродействию другим методам генерации псевдослу­чайных последовательностей из-за необходимости вычисления обратногоэлемента по умножению.1.2.5.ГЕНЕРАТОРЫ ФИБОНАЧЧИЕсли все рассмотренные ранее генераторы были основаны на рекур­рентных зависимостях первого порядка, то генераторы Фибоначчи основы­ваются на использовании рекуррентных зависимостей порядка 2 и выше.Генераторы Фибоначчи широко использовались в различных системахначиная с 1950-х гг.

Однако в 1990-х гг. было обнаружено, что такие генера­торы имеют серьезные статистические отклонения от ожидаемых значенийи при их использовании в методах Монте-Карло порождают недостоверныерезультаты [60].Выходная последовательность генератора Фибоначчи в общем случаеописывается соотношением [6,12]at = (at-r 0 at-s),t = 1,2,...,где:- г и s — значения запаздывания, натуральные числа (г > s ^ 1);- ао, a _ i , . . .

, ot-r+i — целочисленные начальные значения;- 0 — символ бинарной операции, в качестве которой может выступать+, —, • (умножение), ф («исключающее или»).Генератор Фибоначчи с параметрами запаздывания г, s и бинарнойоперацией 0 принято кратко обозначать через F(r,s,Q).Использованиелогических (побитовых) операций в качестве 0 в большинстве случаевнецелесообразно, поскольку при этом каждый бит щ зависит только отодного бита at-rи одного бита ott-s- На практике обычно применяютсяарифметические операции сложения (аддитивные генераторы Фибоначчи)-38или умножения (мультипликативные генераторы Фибоначчи). В случае ис­пользования операций +, — или • вычисления обычно выполняются по мо­дулю 2я, где q — количество двоичных разрядов, используемых в ЭВМ дляпредставления целых чисел.

Кроме того, в случае умножения в качествечленов последовательности обычно используются нечетные целые числа.Известно [17], что если модуль является степенью числа 2 (N = 2 9 ),а многочлен хг + Xs + 1 — примитивный над F2, то максимальный периодТщах выходной последовательности а составляет:- для аддитивных генераторов F(r, s, + ) : Tmax = 2 < 7 _ 1 (2 r — 1);- для мультипликативных генераторов F(r,s, •): Tmax = 2 9 _ 3 (2 Г — 1);- для генераторов с операцией «исключающее или» F(r,s,®):Tmax =r2 -l.Ниже приводится краткий обзор основных наиболее распространен­ных вариантов генераторов Фибоначчи.1.2.5.1.

Характеристики

Список файлов диссертации