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

существует линейный регистр сдви­га длины L, порождающий эту последовательность), то для восстановления-45структуры регистра и его начального заполнения необходимо знать всеголишь 2L следующих подряд членов последовательности а.Таким образом, к достоинствам двоичных линейных регистров сдвигаотносятся простота их реализации, хорошая изученность свойств и боль­шой период, а к недостаткам — низкая скорость работы (не превышающаяодного бита на такт) и малая линейная сложность выходной последова­тельности.1.2.6.3.

О Б О Б Щ Е Н Н Ы Е Р Е Г И С Т Р Ы СДВИГАВ 1973 г. Льюисом и Пэйном [46] был предложен новый генераторпсевдослучайных последовательностей — обобщенный регистр сдвига с об­ратными связями (generalized feedback shift register, GFSR). Появлениеобобщенных регистров сдвига явилось развитием метода генерации псев­дослучайных последовательностей при помощи регистров сдвига с линей­ными обратными связями над полем F 2 .Значениями ячеек обобщенного регистра сдвига являются двоичныевекторы длины q с компонентами из поля F 2 .

Функционирование обобщен­ного регистра сдвига описывается рекуррентной зависимостьюOLt = ot-t-r+s Ф <*t-r,* = 1,2,...,(1.9)где OLi б F | , а символ ф обозначает операцию сложения по модулю 2. Сле­дует отметить, что указанная рекуррентная зависимость по своей струк­туре соответствует выражению (1.7), описывающему регистр сдвига с ли­нейными обратными связями, а также (с точностью до переобозначенияиндексов) рекурренте (1.6), описывающей генератор Фибоначчи с операци­ей «исключающее или».За каждый такт работы обобщенный регистр сдвига вырабатываем qбит выходной последовательности (разрядность q определяется длиной ма­шинного слова ЭВМ), причем для этого требуется три обращения к памятии выполнение всего одной логической операции. Таким образом, генераторявляется быстродействующим, однако обладает существенными недостат­ками:- члены выходной последовательности обобщенного регистра сдвига —-46-векторы cxt — могут рассматриваться как совокупность битовых вы­ходных последовательностей q независимых линейных регистров сдви­га над полем F2, задаваемых рекуррентными соотношениями щ^ =cxij-r+s 0 oa,t-ri t = 1, 2,..., г = 1,..., q, где ац — г-ый компонент век­тора ott\- максимальный период выходной последовательности обобщенного ре­гистра сдвига равен Ттах = 2Г — 1, в то время как максимально воз­можный период для конечного автомата с внутренним состоянием, за­даваемым rq бит памяти (каковым и является обобщенный регистрсдвига длины г с g-битовыми ячейками), равен 2rq.1.2.6.4.

О Б О Б Щ Е Н Н Ы Е Р Е Г И С Т Р Ы СДВИГА С З А К Р У Ч И В А Н И Е МВ 1992 г. Матсумото и Курита [54, 55] предложили новый вариантобобщенных регистров сдвига с обратными связями — обобщенные реги­стры сдвига с закручиванием (twisted generalized feedback shift register,TGFSR), описываемые соотношениемOLt = OCt-r+s 0oct-rA,(1.10)где (Xi G F^—-вектор длины q над полем F2, a A— (q x д)-матрица специ­ального вида с элементами из поля F2, подбираемая таким образом, чтобыее вычисление могло быть эффективно реализовано на ЭВМ. Авторамиработы [54] предложен следующий вид матрицы А:( 0о10о1А =00\CLq-l aq-2(Ло(1.11)0aq-31Умножение на такую матрицу может быть выполнено чрезвычайно быстро. В частности, если ос — (a g _i,a 9 _2, • • •, OCQ) € F2 и а-(aq-i,aq-2, • • - ,ао) G Щ, то вычисление otA можно осуществить следую--47щим образом:_ Jshri(a),а0 = О,I shri(a) 0 a,а0 = 1,где операция shri (а) обозначает сдвиг двоичного вектора а на один раз­ряд вправо.

Таким образом, в процессе работы обобщенного регистра сдви­га осуществляется «закручивание» его внутреннего состояния, и выходнаяпоследовательность уже не может рассматриваться в качестве совокупно­сти выходных последовательностей q независимых регистров сдвига с ли­нейными обратными связями.Обобщенные регистры сдвига с закручиванием обладают следующи­ми преимуществами по сравнению с обычными обобщенными регистрамисдвига:- ячейки памяти регистра могут быть инициализированы произвольны­ми значениями при условии, что среди них будет хотя бы одно нену­левое;- свойства выходной последовательности обобщенного регистра сдвига сзакручиванием полностью определяются его структурой и не зависятот начальных значений;- максимальныйпериодвыходнойпоследовательностисоставляетГ<7Ттах = 2 — 1, и охватывает все возможные состояния регистра, кроменулевого;- выходная последовательность обобщенного регистра сдвига с закручи­ванием равномерно распределена в г измерениях (для сравнения: вы­ходные последовательности линейных конгруэнтных генераторов рав­номерно распределены в лучшем случае в 5 измерениях [6]).1.2.6.5.

В И Х Р Ь М Б Р С Е Н Н АНаибольшее распространение приобрела модификация обобщенныхрегистров сдвига с закручиванием,известная как вихрьМерсенна(Mersenne twister, МТ) [56]. Название генератора обусловлено тем, что ониспользует некоторые свойства простых чисел Мерсенна (т. е. простых чи­сел вида 2Р — 1).Выходная последовательность а вихря Мерсенна описывается рекур--48рентным соотношениемoct = OLt-r+s® (upper g _ f c (a t _ r )||lower f c (a: f _ r + i)) A,£ = 1,2,...,(1.12)где члены последовательности ott 6 Zf — g-разрядные двоичные векторы.Параметрами алгоритма являются порядок рекуррентыг, целые числаs и к (0 < к < д), и (q х д)-матрица закручивания А. Начальное состояниегенератора определяется набором векторов (ско,а_1,... ,o:_ r +i).

Обозна­чение иррегд.(а:) соответствует к старшим битам вектора a., loweiq-k(ot) —(q — к) младшим битам, а операция || — конкатенации двоичных векторов.Матрица А имеет тот же вид, что и в случае обобщенных регистров сдвигас закручиванием (1.11).Отметим, что при к = 0 выражение (1.12) принимает вид (1.10), т.е.вихрь Мерсенна «вырождается» в обобщенный регистр сдвига с закручи­ванием, а при к — 0 и А = I — в обобщенный регистр сдвига (1.9).Как уже отмечалось в разделе 1.2.6.4, вычисление произведения аАсводится к логическому сдвигу двоичного слова на один разряд и побито­вой операции «исключающее или».

Операции взятия старших и младшихчастей двоичных векторов может быть выполнена при помощи логическийопераций «и» и «или». Таким образом, вычисление рекурренты (1.12) осно­вывается только на использовании логических и сдвиговых операций, чтообеспечивает генератору высокую скорость.Вихрь Мерсенна предназначен, в первую очередь, для использованияв задачах симуляции методом Монте-Карло, и члены выходной последо­вательности генератора в дальнейшем обычно отображаются на отрезокт[0,1) C l при помощи преобразования д(х) = х/2 ,т ^ q.

Для улуч­шения свойств распределения каждый член выходной последовательностиa = { a t G Z | } перед применением д{х) умножается справа на обратимуюперемешивающую матрицу Т (см. также [55]):f3t = OLtT.-49Матрица Т реализует последовательность следующих преобразований:w= oct®shrh(at),(1.13)w= ги © (shl;2(u>) Л и ) ,(1-14)ги = w © (shlfe(w) Лг>),(1.15)/3t = u>0shrf 4 (w),(1.16)где h, h, h и U — целые числа, определяющие величины сдвигов, w — про­межуточные значения преобразований, и и v — g-разрядные битовые мас­ки, shli(w) и shr/(io) — логический сдвиг двоичного слова w на I разрядоввлево и вправо соответственно, Л — операция логического «и».

Преобразо­вания (1.14) и (1.15) были предложены в [55] для обобщенных регистровсдвига с закручиванием, а (1.13) и (1.16) добавлены при разработке вихряМерсенна.Существует несколько модификаций вихря Мерсенна, отличающихсяпараметрами. Наиболее часто используется т.н. алгоритм МТ19937 [56], вкотором:q = 32,а = 0x9908B0DF,h = 11,г = 624,u = Ox9D2C5680,l2 = 7,s = 397,v = 0xEFC60000,/3 = 15,к = 31,U = 18(вектор о = {aq-\, a g _2,..., ao) соответствует нижней строке матрицы А).Алгоритм МТ19937 обладает следующими достоинствами:- он эффективно вычислим на 32-разрядных ЭВМ и не требователен кобъему памяти (внутреннее состояние занимает 624 32-битных слова);- период выходной последовательности имеет огромное значение Т =219937 _ 1 ~ ю6001, что на много порядков превосходит текущие по­требности;- выходная последовательность обладает хорошими статистическимисвйоствами: в частности, она успешно проходит статистические тестыиз набора DIEHARD и является равномерно распределенной в 623 из--50мерениях.Тем не менее, следует отметить, что вихрь Мерсенна не может напря­мую использоваться в качестве криптографического генератора псевдослу­чайных чисел из-за предсказуемости выходной последовательности; основ­ной областью применения генератора авторы работы [56] считали методыМонте-Карло.1.2.6.6.

Р Е Г И С Т Р Ы СДВИГА С Н Е Л И Н Е Й Н Ы М И О Б Р А Т Н Ы М И С В Я З Я М ИСтруктура регистра сдвига с нелинейными обратными связями (non­linear feedback shift register, NLFSR) приведена на рис. 1.4. Для вычисле­ния очередного состояния регистра и символа выходной последовательно­сти используется нелинейная функция обратной связи /:at = f(cxt-i, «i-2, • • •, ott-ь),где L — длина регистра.1а,2«м«Г-2L«/-3Щ-L'г•'^3^^'^-гat-L''^Рис.

1.4. Регистр сдвига с нелинейными обратными связямиХотя возможно построение регистров над произвольным множествомзначений, обычно нелинейные регистры реализуются над полем F2. Функ­ция / в таком случае является булевой и задает отображение/ : F^ —> F2.К достоинствам нелинейных регистров сдвига относятся:- эффективность и простота реализации (в первую очередь аппаратной);- непредсказуемость (в случае неизвестности функции /) и высокая ли­нейная сложность последовательности.Тем не менее, нелинейные регистры сдвига обладают и существенныминедостатками, связанными со слабой изученностью их свойств:- сложность обеспечения хороших статистических свойств выходной по­следовательности ;-51- сложность предсказания периода для конкретного начального состоя­ния.Для преодоления указанных недостатков используются различныеподходы.