5.ПолучениепростыхчиселдляалгоритмаRsa Процедураполученияустойчивыхпростыхчисел

1.Генерируютсяпростыечислаs,t

2.Получаемпростоечислоrтакоечто,(r-1)делитtбезостатка:r-1|t

Наосновеэтихдвухоперацийполучаемпростоечислорпоследующейформуле:

P=U(r,s)+krs,гдеk–подборноенатуральногечисло

Числордолжноудовлетворятьследующимсвойствам:

 p≡1modr

 p≡(s-1)mods

 U(r,s)=(s^r-1–r^s-1)modrsr,s,t–простыечисла

Числорназываетсяпростымустойчивым,еслионоудовлетворяетследующимусловиям:

1.р≡1modr

2.p≡(s-1)mods

3.r≡1modt

Числаr,s,должныудовлетворятьследующимкритериям:

1.r≡(u-1)modu

2.s≡1modw

3.s≡(v-1)modv,гдеu,v,w–простыечисла

Пример:р=19819=2·3·3·17·653+1=2·2·5·97·103-1

р–устойчивоепростоечисло

Лекция15

1.Генераторыпсевдослучайныхпоследовательностей

_{надполем}

_GF(2)

М-последовательности.ГПСЧтипаЛРС1

_{Определение. Последовательностью над полем}

_GF(p)

_будем

называть любую функцию

^U_p^:NF_p^{, заданную на множестве N и}

_{принимающуюзначениявполе}

_GF(p).

Рассмотримкласспоследовательностей

^U_p^{,получаемыхнаоснове}

схемылинейногорегистрасдвигасобратнойсвязью(ЛРС),изображеннойна

_{рис.2.1.Схемасодержитn-разрядныйрегистрсдвига(запоминающиеячейки}

регистраобозначенысимволами

^T₁^,

^T₂^,…,

^T_n^{),сумматоры,обозначенные}

_{символом,помодулюдвавцепиобратнойсвязиицепи(отводы)с}

коэффициентамипередачи

^a_i^{0,1},

i1,n.Если

^a_i^{0,этоэквивалентно}

отсутствию(наличиюпри

^a_i^{1)связимеждувыходомi-горазрядарегистра}

^{ивходомi-госумматора.Символa}₀

принимаетзначения0или1.Схему,

_{изображеннуюнарис.2.1,обозначимсимволомЛРС1.}

^{x1 x2 x}_n

T₁ T₂

_{. . .} ^T_n

a₁ a₂

. . . ^a_n

^a₀

_{Рис.2.1.СхемаЛРС1}

Вочередномтактеработырегистрадвоичныесимволы

^x₁^,

^x₂^,…,

^x_n^,

_{содержащиеся в его ячейках, умножаются на соответствующие}

коэффициентыa_i

исуммируютсяпомодулюдва,послечегопроисходит

^{сдвиг(вправо)информацииврегистре,авосвободившуюсяячейкуT}₁

записывается вычисленное значение суммы. Двоичные наборы

x_1,x_2,...,x_n,снимаемыевкаждыйтактработысхемысвыходовячеекрегистра,можнорассматриватькакдвоичныеn-разрядныецелыечисла.

_{Последовательностьдвоичныхсимволов,снимаемыхсвыходаодного}

^{(любого)разрядарегистраявляетсяпоследовательностьюU}_p

надполем

GF(2).Такиепоследовательностиназываютлинейнымирекуррентнымипоследовательностями(ЛРП).

^{Устройство,реализованноепорассмотреннойсхеме,принятоназывать}

генератором псевдослучайных чисел или генератором псевдослучайныхпоследовательностей.

Начальноезаполнениеячеекрегистрадвоичнымисимволамиявляется

_{начальнымсостояниемрегистра.}

Введемследующиеобозначения.

^X(t₀⁾

–n-разрядныйдвоичныйвектор,

начальноесостояниерегистра.

_{однихнулей(нулевойвектор).}

X_0–начальноесостояние,состоящееиз

Пусть

^a₀^{0, тогда состояние схемы в момент времени}

t1

описываетсяследующейсистемойуравнений

_{x1(t1)a1x1(t)a2x2(t)...an1xn1(t)anxn(t)}

x

2

_

^ (t1)

^x₁^(t)

^x₃^(t1)

^_...

^_^x_n^(t1)

^x₂^(t)

x_n1(t).

_{Полученнуюсистемууравненийможнозаписатьвматричномвиде}

^X(t1)A_T^{X(t), (2.1)}

_{a a}

_{... a a}

_

_{x1(t1)}

_x1(t)

_1 2

n1 n_

_где

_X(t1)^_x2

_(t1)^

_X(t)^_x2

_(t)^

1

_{A 0}

0 ... 0 0

_{1 ... 0 0 .}

_

_,

_

_{ ... }

_{ ...}

^T _...

_{... }

_

_,

_xn(t1)_

_xn(t)_

_

^{0 0}

_

^{... 1 0}

^{Квадратную матрицу A}_T

размера n называют характеристической

матрицейГПСЧ,изображенногона рис.2.1.ЭлементыпервойстрокиматрицыопределяютструктуруобратныхсвязейсхемыГПСЧ.

Последовательности,порождаемыеГПСЧ,являютсяпериодическими,тоестьчерезопределенноеколичествотактов(сдвигов)последовательность

_{повторится.}

^{Определение. Периодом последовательности U}_p

называют

_{наименьшеечисло}

_{LN,длякоторогосуществуетнатуральноечисло}

_K0

такое,чтодлявсех

i0

справедливоравенство

^U_p^{(KiL)U}_p^(Ki).

^{МаксимальныйпериодпоследовательностиU}_p

длясхемыГПСЧравен

2^n1.Всамомделе,при

^a₀^0

начальноесостояниерегистра

X(0)

^{порождаетпоследовательностьU}_p^{,состоящуюизоднихнулей(запрещенное}

_{состояние),ачислоразличныхзаполненийрегистрадлиныnравно}

₂ⁿ_.

Однако,взависимостиотструктурыобратнойсвязииотначальногосостояния регистра, период последовательности может быть иным (в

_{частности,дажеединичным(L=1)).}

^{Определение.ПоследовательностьU}_p

надполем

GF(2),получаемая

_{посоотношению(2.1)иимеющаямаксимальныйпериод}

₂ⁿ_{1,называется}

максимальной линейной рекуррентной последовательностью - M -

_{последовательностью.}

При

^a₀^1

состояниерегистра

X(0)

неявляетсязапрещенным.Вэтом

случаеначальноесостояниерегистра,состоящееизвсехединиц,являетсязапрещенным, поскольку порождает последовательность U, состоящую

_{также из одних единиц. При других начальных состояниях}

_{последовательностьUнадполем}

_GF(2)

_{такжеимеетмаксимальныйпериод}

2^n1,ноявляетсяинверснойпосравнениюсM-последовательностью.

_{ПериодЛРПопределяетсяхарактеристическиммногочленомнадполем}

GF(2)

матрицы

A_T:

^{f(x)xna}₁

2

_xn1_a

x^n2...a

_n1

^xa_n

, (2.2)

которымявляетсяопределительматрицы

^(A_T^{XE),гдеЕ–единичная}

^{матрицаразмераn.Коэффициентыa}_i

многочлена

f(x)

определяютпервую

строкуматрицы A_T

_{полинома(2.2)).}

(матрицу A_T

называютсопровождающейматрицей

_{Еслихарактеристическиймногочлен}

_f(x)

_{надполем}

_GF(2)

_{является}

_{неприводимымипримитивным,топериодЛРПравен}

₂ⁿ_1.

Замечание.Таблицапримитивныхмногочленовдлястепени

_{приведенавПриложении1,всоответствиис[9].}

n1,127

Определение. Наименьший из всех возможных периодов ЛРП

_{называетсяминимальнымеепериодом.}

_{Если характеристический многочлен}

_f(x)

_{является только}

_{неприводимым,томаксимальныйпериодЛРП,вэтомслучае,}

_Lord

_f2ⁿ_1.

НачальнойинформациейдляпостроенияГПСЧ,порождающегоЛПРс

_{заданным периодом L, является характеристический многочлен (2.2) с}

ord

fL.

Пример2.1.Пустьзаданпримитивныймногочлен

^P₁^(x)x4

x³

1.

_{СоответствующаясхемаГПСЧизображенанарис.2.2а.}

^x₁ ^x₂ ^x₃ ^x₄

^T₁ ^T₂ ^T₃

Рис.2.2а.СхемаГПСЧ,соответствующая

P₁₍x)x⁴

x^31

Пусть для этой схемы

^X(t₀^{)1001. В табл. 2.1 представлена}

периодическаяпоследовательностьвекторов

^X(t_i^),

i0,14,снимаемыхс

выходов

x_1,

x_2,

x_3,

x₄₍диаграммыработыГПСЧ),с

L15.

_{Таблица2.1(начало)}

	X(t0)	X(t1)	X(t2)	X(t3)	X(t4)	X(t5)	X(t6)
x1	1	0	0	0	1	1	1
x2	0	1	0	0	0	1	1
x3	0	0	1	0	0	0	1
x4	1	0	0	1	0	0	0

При других начальных состояниях

^X(t₀^)X₀

получим 15

последовательностейвекторов

^X(t_i⁾

спериодомL=15,различающихся

некоторымсдвигомотносительнодругдруга.

_{Таблица2.1(окончание)}

	X(t7)	X(t8)	X(t9)	X(t10)	X(t11)	X(t12)	X(t13)	X(t14)
x1	1	0	1	0	1	1	0	0
x2	1	1	0	1	0	1	1	0
x3	1	1	1	0	1	0	1	1
x4	1	1	1	1	0	1	0	1

Двоичнаяпоследовательность,снимаемаясодноговыхода

_{являетсяпоследовательностьюUнадполемGF(2).}

x_i,

i1,4,

Пример . Пусть задан примитивный многочлен

^P₂^(x)x4

x1.

СоответствующаясхемаГПСЧизображенанарис.2.2бидиаграмма-втабл.

_2.2.

^x₁ ^x₂ ^x₃ ^x₄

^T₁ ^T₂ ^T₃

Рис.2.2б.СхемаГПСЧ,соответствующая

P₂₍x)x⁴

x1

_{Пример2.3.Пустьзаданхарактеристическийнеприводимыймногочлен}

_g(x)x⁴_x³_x²_{x1.Порядокэтогомногочлена}

_{ordg5,таккак}

_g(x)

_{являетсяделителеммногочлена}

_x⁵_1,т.е.

x^51(x^4x^3x^2x1)(x1).

_{Таблица2.2(начало)}

	X(t0)	X(t1)	X(t2)	X(t3)	X(t4)	X(t5)	X(t6)	X(t7)
x1	1	1	0	1	0	1	1	1
x2	0	1	1	0	1	0	1	1
x3	0	0	1	1	0	1	0	1
x4	1	0	0	1	1	0	1	0

_{Таблица2.2(окончание)}

	X(t8)	X(t9)	X(t10)	X(t11)	X(t12)	X(t13)	X(t14)
x1	1	0	0	0	1	0	0
x2	1	1	0	0	0	1	0
x3	1	1	1	0	0	0	1
x4	1	1	1	1	0	0	0

_{СхемаГПСЧ,соответствующая}

_{g(x),представленанарис.2.3.}

^x₁ ^x₂

^x₃ ^x₄

^T₁ ^T₂ ^T₃

_{Рис.2.3.СхемаГПСЧдля}

_g(x)x⁴_x³_x²_x1

Даннаясхемавзависимостиот

^X(t₀^),

^X(t₀^)X₀^{,порождаеттри}

_{диаграммысостояний,представленныхвтабл.2.3,соднимитемже}

_{периодом}

_L5.

_{Замечание 2.2. М-последовательности имеют статистическую}

равномерностьнапериоде

L2^n1,тоестьчислоединиц

^N₁^{инулейN}₂

определяетсявеличинами

N_12

n1_и

N_22

n1

1.

^x₁^x₂^x₃^x₄

^x₁^x₂^x₃^x₄

Таблица2.3

^x₁^x₂^x₃^x₄

1110	0110	0010
1 1 1 1	0 0 1 1	1 0 0 1

1 1 1 1

0 0 1 1

1 0 0 1

0	1	1	1	0	0	0	1	0	1	0	0
1	0	1	1	1	0	0	0	1	0	1	0
1	1	0	1	1	1	0	0	0	1	0	1