Математические основы криптологии

• Название: Математические основы криптологии
• Дата: 29.01.2022
• Размер: 1.3 Mb.
• Имя файла: 31915_aac6dc94845edad44fd9404106e280c1.docx
• Тип: Учебно-методическое пособие; #345823
• страница: 6 из 12

5. Элементы теории конечного поля. Основные

понятия и теоремы.
Поле.

Определение. Отображение : RS кольца R в кольцо S называется гомоморфизмом, или для любых a,b  R

(a+b)= (a)+ (b) и (ab)= (a)(b).

Таким образом, гомоморфизм : RS сохраняет обе операции + и . кольца R.

Определение. Для простого числа Р обозначим через F_P множества {0,1,2,...,P -1} целых чисел, и пусть отображение : Z/pF_p определяется условием ([a])=a для a=0,1,2,...,P -1. Тогда множество F_P со структурой поля, индуцированной отображением , называется полем Галуа порядка P. (Такое поле еще обозначают GF(p) – аббревиатура от слов Galois и Field(поле)).

Отображение : Z/pF_p является изоморфизмом т.к. ([a]+[b])= ([a])+ ([b]) и ([a][b])= ([a])([b]). Нулем конечного поля GF_p будет 0 ноль, а единицей – единица 1 и его структура совпадает со структурой поля Z/p.

Пример. Важным является пример конечного поля GF_p второго порядка. Элементами этого поля являются 0 и 1 - бинарные элементы, для которых выполняются операции

	0 1			0 1
0 1	0 1 1 0		0 1	0 0 0 1

В связи с использованием для вычислений ЭВМ не менее важным является поле Галуа из элементов {0,1}, обозначаемое GF(2^N) и соответствующие строкам данных длиной N бит. Такие строки бит удобно рассматривать в виде многочленов. Например, байт из 8 бит можно представить (10010101)=x⁷+x⁴+x²+1.

Определение. Пусть R произвольное кольцо. Если существует такое натуральное число n, что для каждого rR выполняется равенство nr=0, то наименьшее из таких чисел n (например, n₀) называется характеристикой кольца R, а само R называют кольцом характеристики n₀.

Теорема. Если кольцо R{0} с единицей е и без делителей нуля имеет положительную характеристику n, то n – простое число.

Следствие. Характеристикой конечного поля является простое число.

Теорема. Пусть R – коммутативное кольцо простой характеристики p. Тогда

; ; и .

Выясним теперь, каким должен быть идеал М коммутативного кольца R с единицей, чтобы фактор -кольцо R/M было полем.

Пусть R – коммутативное кольцо с единицей. Элемент aR называется делителем элемента bR, если существует элемент сR такой, что ас=b. Делители единицы называются обратимыми элементами a ^-1. Элементы a и b из R называют ассоциированными, если  обратимый элемент rR такой, что a=br. Элемент cR называется простым элементом кольца R, если он не является обратимым элементом и не имеет других делителей, кроме ассоциированных с ним элементов или обратимых элементов. Идеал pR кольца R называют простым идеалом, если для a,bR включение abP имеет место лишь в том случае, когда либо aP, либо bP. Идеал MR кольца R называется максимальным идеалом, если  идеала J кольца R включение влечет за собой J=M или J=R. Кольцо R называют кольцом главных идеалов, если оно является целостным кольцом, и каждый идеал J кольца R является главным, т.е.  элемент aR такой, что J=(a)={rarR}.

Как уже указывалось на прошлых лекциях, важную роль в криптографических приложениях играют многочлены и наиболее важные и интересные результаты по ним получены в теории конечного поля.

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

,

где n – целое неотрицательное число – степень многочлена,

a_i – элементы кольца (коэффициенты многочлена),

x – переменная или неизвестная не принадлежащая кольцу.

Следует отметить, что при обычном определении многочлена связь между коэффициентами a_i и переменной x обычно не обсуждается. Однако такая связь существует и возможно ее показать в рамках абстрактной алгебры, давая определение многочлена как элемента кольца многочленов.

Определение. Кольцо S, образованное многочленами над кольцом R, называется кольцом многочленов над R и обозначается R[x].

Рассмотрим множество S всех бесконечных последовательностей вида (a₀,a₁,...,a_n,...), компонентами a_i которого является элементы коммутативного кольца R с единицей 1, причем лишь конечное число компонент a_i может быть отлично от 0. Это множество образует коммутативное кольцо с единицей относительно операций + и . Кольцо R таким образом можно рассматривать как подкольцо кольца S, а S – как расширение кольца R. Элементами кольца S являются многочлены , определяемые как бесконечные последовательности с конечным числом ненулевых элементов.

При этом переход от кольца R к кольцу многочленов S над R называется кольцевым присоединением элемента x к кольцу R. Таким образом, отображается связь между элементами кольца R (коэффициентами многочлена a_i) и новым элементом x.

В дальнейшем изложении в основном будем иметь дело с многочленами над полями F, поэтому для кольца многочленов над полем F будем использовать обозначение F[x] или G F[x].

Для кольца многочленов над полем справедливы операции +, , сравнения, деления с остатком, делимость:

Два многочлена и  F[x] над полем F считаются равными тогда и только тогда, когда

, , и для .

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

,

а произведение многочленов и

, .

Деление: многочлен g(x)F[x] делит многочлен f(x)F[x] если существует h(x)F[x] такой, что f(x)=g(x)h(x).

Деление с остатком. Пусть g(x)0 – многочлен из F[x] над полем F. Тогда для каждого f(x)F[x] существуют такие многочлены q(x) и r(x) F[x], что

f(x)=q(x)g(x)+r(x) (deg(r)

Простые элементы кольца многочленов F[x] обычно называют неприводимыми многочленами.

Определение: Многочлен f(x)F[x] называется неприводимым над полем F или в кольце F[x], если он имеет положительную степень и равенство f(x)=g(x)h(x); g(x),h(x)F[x] может выполнятся лишь в том случае, когда либо g(x), либо h(x) являются постоянными многочленами (т.е. имеют степень и являются константами).

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

Примеры:

1. 
   Многочлен f(x)=x² -2 Q неприводим над полем рациональный чисел Q, но приводим над полем действительных чисел R т.к. .
   
2. 
   Многочлен f(x)=x²+x+1 неприводим над полем Галуа GF(r) т.к. f(0)=f(1)=1, но приводим над его расширением GF(4).
   

Неприводимые многочлены играют важную роль в устройстве кольца, т.к. каждый многочлен из F[x] может быть представлен, причем единственным способом, в виде произведения неприводимых многочленов. Эти неприводимые многочлены являются, по сути дела, аналогами простых чисел, через произведение которых можно выразить любое натуральное число n>1 (основная теорема арифметики).

В нашем дальнейшем изложении применительно к криптосистемам особенный интерес будут представлять многочлены неприводимые степени n над простыми полями F_p порядка p, где p – простое число. Поиск всех неприводимых многочленов заданной степени n над некоторым полем F_p или GF(p) представляет собой очень сложную задачу. Французский математик Эварист Галуа (1811 -1832гг) создал теорию (теорию поля Галуа), доказывающую существование неприводимых многочленов сколь угодно большой степени, но поиск таких многочленов - очень сложная задача, и криптографические службы всего мира ведут активную работу по поиску таких многочленов, но эти работы засекречены. Известен неприводимый многочлен степени x⁶¹+ x³+1, а для n>61 данных найти не удалось. Чтобы более подробно осветить вопросы нахождения неприводимых многочленов над конечными полями, вопросы разложения многочленов на множители над конечными полями и связанные с ними проблемы построение линейных рекуррентных последовательностей над конечными полями, которые лежат в основе построения современных криптосистем, продолжим знакомство с основными понятиями и элементами теории конечного поля.

Определение. Пусть F – произвольное поле и f(x)F[x]. Тогда замена переменной x в многочлене f(x) произвольным элементом bF обращает этот многочлен в корректно определенный элемент поля F. Если f(x)=a₀+a₁x+...+a_nxⁿF[x] и bF, то, заменяя x на b, получаем элемент f(b)=a₀+a₁b+...+a_nbⁿF. Элемент f(b) называют значением многочлена f(x) при x=b. Если в кольце F[x] имеется какое -либо полиномиальное равенство, то заменяя в нем x на bF, получаем равенство в поле F. (Принцип подстановки). Тогда: элемент bF называют корнем (или нулем) многочлена f(x)F[x], если при x=b f(b)=0.

Теорема (устанавливает связь между корнями и делимостью). Элемент bF является корнем многочлена f(x)F[x] тогда и только тогда, когда многочлен x -b делит f(x) (т.е. x -bf(x)).

Определение. Пусть bF - корень многочлена f(x)F[x]. Кратностью корня b называют такое натуральное число K=(1,2,...), что f(x) делится на (x -b)^K , но не делится на (x -b)^K+1. При K=1 корень называют простым, а при K>1 – кратным.

Определение. Производной многочлена f(x)=a₀+a₁x+a₂x²+...+a_nxⁿF[x] называется многочлен f’(x)=a₁+2a₂x+...+na_nx^{n -1}F[x]. Отсюда следует теорема.

Теорема. Корень bF многочлена fF[x] является кратным тогда и только тогда, когда он одновременно является и корнем производной f’(x) многочлена f(x).

Существует связь между отсутствием или несуществованием корней и неприводимостью многочленов. Если f(x) - неприводимый многочлен из F[x] степени n2, то согласно теореме  он не имеет корней в поле F. Обратное утверждение справедливо только для многочленов степени 2 и 3.

Теорема. Для неприводимости многочлена f(x)F[x] степени 2 и 3 в кольце F[x] необходимо и достаточно, чтобы он не имел корней в поле F.

Пример: Пользуясь этой теоремой, можно найти неприводимые многочлены степени 2 и 3 в кольце F₂[x] над конечным полем F₂, путем исключения из всей совокупности многочленов указанной степени, принадлежащих кольцу F₂[x], тех многочленов, которые имеют корни в поле F₂. Напомним, что элементами поля F₂ или GF(r) являются {0,1}. Тогда очевидно, что в кольце F₂[x] имеется только один неприводимый многочлен степени 2: f(x)=x²+x+1 и два неприводимых многочлена степени 3: f(x)=x³+x+1, x³+x²+1.

Действительно: многочлены степени 2 – это f₁=x²+1, f₂=x²+x, f₃=x²+x+1.

Подставляя в них вместо x элементы в поля GF(r), т.е. 0 или 1, видно, что f₁=0 при x=1, f₂=0 при x=1 и x=0, а f₃0 при любом x{0,1}. Тоже самое и для многочленов степени 3: f₁=x³+x²+x+1, f₂=x³+x²+1, f₃=x³+x+1, f₄=x³+x²+x, f₅=x³+x²…

Наряду с многочленами f(x) от одной переменной х, рассматривают многочлены от нескольких переменных. Пусть R - коммутативное кольцо с единицей, и пусть х₁,...,х_n символы, которые выступают в качестве переменных, образуем сначала кольцо многочленов R[x₁], затем кольцо R[x_1,x₂]=R[x₁]R[x₂] и т.д. пока не получим R[x₁,...,x_n]=R[x₁,...,x_{n -1}]R[x_n]. Элементами кольца R[x₁,...,x_n] являются выражения

f(x₁,...,x_n)= a_i1...inx₁ⁱ¹...x_nⁱⁿ

с коэффициентами а_i1...inR, причем суммирование распространяется на конечное множество n наборов (i₁,...,i_n) неотрицательных целых чисел и соблюдается соглашение x_j⁰=1, 1jn. Такое выражение называют многочленом от переменных х₁,...,х_n над кольцом R. Два многочлена f и g из R[x₁,...,x_n] равны, когда равны все соответствующие коэффициенты. При этом предполагается, что переменные х₁,...,х_n перестановочны друг с другом, так что, например, выражения x₁ х₂ х₃ и х₃ х₁ х₂ отождествляются.