Научная литература
booksshare.net -> Добавить материал -> Криптография -> Алферов А.П. -> "Основы криптографии Учебное пособие" -> 66

Основы криптографии Учебное пособие - Алферов А.П.

Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии Учебное пособие — М.: Гелиос АРВ, 2002. — 480 c.
ISBN 5-85438-025-0
Скачать (прямая ссылка): osnovikriptografii2005.djvu
Предыдущая << 1 .. 60 61 62 63 64 65 < 66 > 67 68 69 70 71 72 .. 126 >> Следующая


Для конечного поля из q элементов б>дем использовать

стандартное обозначение GFiq) .

Утверждение 1. Если F(x) — неприводимый многочлен над

полем GF(2) степени т , и 2т — 1 — простое число, то F(x) —примитивный многочлен.

Доказательство. Из неприводимости многочлена F(x) следует, что единица поля GF (2т) (которое является его полем разложения) не является корнем этого многочлена. Так как по условию (2т ~ 1) — простое число, все элементы поля GF(2м) , отличные от единицы, имеют в мультипликативной группе этого поля порядок 2т -1. Следовательно, F(x) — примитивный многочлен.

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

Утверждение 2. Неприводимый многочлен F(x) примитивен в том и только в том случае, когда для любого простого чис-

чт-\

ла р, делящего qm -1, многочлен х р не сравним с 1 по модулю многочлена F(x).

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

254
I юточные системы шифрования

характера. На практике используются таблицы неприводимых и примитивных многочленов над конечными полями (см., например, [Неч99]).

Закон рекурсии дает удобный способ вычисления очередного знака ЛРП через предыдущие, но при изучении ее свойств более предпочтительной формой задания является формула общего члена последовательности, представляющая собой аналитическое выражение члена последовательности в виде функции от его номера. Рассмотрим этот способ представления на примере ЛРП над конечными полями с неприводимыми характеристическими многочленами.

Пусть P = GF(q) и Q —поле из qm элементов, являющееся расширением поля P. Тогда функцией “след” из поля

т

Q в поле P называется отображение trfj (a) :Q —> P вида

В силу свойств конечных полей справедливы равенства

(Fq (x)f = trq (*) -

т т т

< (ах + by) = а¦ tr$ (x) + b-trfj (у), a,beP,

означающие, что функция “след” является линейным отображением над полем P.

Лемма 1. Для любого ненулевого а є P и любого be P

т

число решений уравнения trfj (a x) = b равно qm .

Доказательство. Обозначим через Nh число решений рассматриваемого уравнения. Тогда для любого b є P выполняется неравенство Nh < qm~x, так как qm~x — степень мно-

255
І лава 9

гочлена tr* (ci’x)-b9 а многочлен над полем не может

иметь корней больше, чем его степень. С другой стороны, для

т

любого X є P значение tr^ (a • х) лежит в поле P, а значит,

т

X является корнем уравнения tr{j (a • х) = b при некотором подходящем значении b . Следовательно,

IAWm-

beQ

tn—I

Полученное равенство (при условии, что Nb <q для любого Ъ ) может выполняться только в том случае, если для всех значений b имеет место равенство Nb — qm ]. Лемма доказана.

т-1

Теорема 1. Пусть F(x) = Xm — неприводи-

J=О

мый многочлен над полем P степени т, в —корень F(x) в поле Q. Тогда для ЛРП {u(l)} с характеристическим многочленом F(x) существует единственная константа а є Pt такая, что

т

U(I) = tr* (а-в1), />0. (4)

Доказательство. То, что последовательность элементов поля, заданная формулой (4), является линейной рекуррентной последовательностью с характеристическим многочленом F(x) , следует из равенств

256
I юточные системы шифрования

т-1 т-1

Yfj ' + J)=Yl]' tVq іa ' 0>+J ) =

J=O 7=0

trCI

qm

f I л

m-1

a-9, j4fjeJ

J=0 У

Заметим, что число всех линейных рекуррентных последовательностей с характеристическим многочленом F(x)

равно qm. Ровно столько же существует и различных констант из поля Q. Из количественных соображений для завершения доказательства теоремы достаточно показать, что при разных константах а из поля Q будут получаться различные последовательности.

Если для двух различных констант ах и а2 выполняется равенство

т , т

tfq («1 -0) = trfj (a2 ¦ в ), />0,

то, пользуясь линейностью функции след, получаем соотношение

т

((°| ~о2)'в ) = 0, />о,

которое противоречит лемме 1. Теорема доказана.

Пусть и — ЛРП максимального периода над полем P и v(al,...,ak) — число решений системы уравнений

257
Гпава 9

I u(i + j) = aJ, j = I,k,

[0<i<qm-l,

то есть число появлений мультиграммы Qf1,...9ак на периоде последовательности и.

Утверждение 3. Пусть F(x) — примитивный многочлен степени т над полем P и в — корень F(x) в поле Q. Тогда любая ненулевая мультиграмма ) встреча-

ется на периоде ЛРП и ровно

v(ax,...,ak) = qm~k

раз, а число вхождений нулевой мультиграммы на единицу меньше.

Доказательство. Так как порядок элемента в равен

qm — 1, то множество {в1, / = — 2} содержит все нену-

левые элементы поля Q. Поэтому из представления знаков ЛРП и в виде

u(i) = trf (а -в1), аеР,

следует, что значение v(at,...,cгк) равно числу ненулевых решений в поле Q системы уравнений
Предыдущая << 1 .. 60 61 62 63 64 65 < 66 > 67 68 69 70 71 72 .. 126 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed