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

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

Определение. Пусть многочлен f(х₁,...,х_n) R[x₁,...,x_n] задан выражением

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

Если a_i1...in0,то a_i1...inx₁ⁱ¹...x_nⁱⁿ называется членом многочлена f(x₁,...,x_n), а i₁+...+i_n - степенью этого члена. Степень многочлена f(x₁,...,x_n) (deg(f)) определяется как наибольшая из степеней его членов. Для f(x₁,...,x_n)=0 полагают deg(f)= -. Если f(x₁,...,x_n)=0 и все члены f имеют одну и туже степень, то многочлен f называют однородным.

Определение. Многочлен f(x₁,...,x_n) R[x₁,...,x_n] называется симметрическим, если для любой перестановки i₁+...+i_n целых чисел 1,...,n выполняется равенство

f(x_i1,...,x_in)= f(x₁,...,x_n).

Введем несколько понятий, связанных с расширением полей, о котором мы немного говорили ранее.

Пусть F поле. Подмножество К поля F, которое само является полем относительно операций поля F, называется его подполем. В этом случае поле F называется расширением поля К.

Если KF, то К – собственное подполе поля F.

Если К - подполе конечного поля F_p при простом Р, то оно должно по определению содержать элементы 0 и 1, а значит, и все другие элементы поля F_p в силу замкнутости поля К по сложению. Следовательно, поле F_p не имеет собственных подполей, отсюда следующее определение: поле, не содержащее собственных подполей называется простым полем. Любое конечное полеF_p порядка Р при простом Р есть простое поле.

Определение. Пусть К - подполе поля F и М – любое подмножество поля F. Тогда поле К(М) определим как пересечение всех подполей поля F, содержащих одновременно К и М: оно называется расширением поля К, полученным присоединением элементов множества М. В случае конечного множества М={_1,...,_n} будем писать К(М)=К(_1,...,_n). Если М состоит из одного элемента F, то поле L=K() называют простым расширением поля К, а элемент F - образующим элементом простого расширения L поля К.

Определение. Пусть К – некоторое подполе поля F и F. Если  удовлетворяет нетривиальному полиномиальному уравнению с коэффициентами из поля К, т.е. если a_nⁿ+...+a₁+a₀=0, где элементы a_i лежат в К и не равны нулю одновременно, то элемент  называется алгебраическим над К. Расширение L поля К называется алгебраическим расширением поля К, если каждый элемент поля L является алгебраическим над К.

Одним из наиболее фундаментальных результатов, относящимся к понятию расширения полей является теорема Кронежра:

Пусть многочлен f(x) K[x]неприводим над полем К. Тогда существует простое алгебраическое расширение поля К, образующим элементом которого является некоторый корень f(x).

Эта теорема гарантирует для любого неприводимого над полем F существование такого расширения поля F, в котором этот многочлен имеет корень.

Рассмотрим теперь вопросы строения конечных полей, опишем их основные свойства и методы построения.

6. Элементы теории конечного поля. Строение

конечных полей. Основные свойства и методы

построения конечных полей.
Из предыдущих лекций вспомним, что для каждого простого числа Р фактор кольцо Z/(р) является конечным полем, состоящим из Р элементов, которое отождествляют с конечным полем Галуа F_р или GF(p) порядка р. Эти поля играют важную роль в теории полей, так как каждое поле характеристики р должно содержать изоморфное F_р подполе и потому может рассматриваться как расширение поля F_р.

Рассмотрим вопрос о числе элементов конечного поля.

Лемма 1. Пусть F - конечное поле, содержащее подполе К из q элементов. Тогда F состоит из q^m элементов, где m=[F:K].

Здесь [F:K] обозначает степень поля F над К, т.е. размерность пространства F над К. Если рассматривать F как векторное пространство над полем К.

Теорема. Пусть F - конечное поле. Тогда оно состоит из рⁿ элементов, где р простое число, являющееся характеристикой поля F, а n - натуральное число, являющееся степенью поля F над его простым подполем.

Доказательство этой теоремы достаточно простое и приводится, чтобы вспомнить материал прошлой лекции. Так как поле F конечно, то его характеристика есть некоторое простое число р. Поэтому простое подполе К поля F изоморфно F_р и значит содержит р элементов и, следовательно, согласно лемме 1, поле F содержит рⁿ элементов.

Лемма 2. Если F - конечное поле из q элементов, то каждый элемент аF удовлетворяет равенству а^q=а.

Лемма 3. Если F - конечное поле из q элементов и К - подполе поля F, то многочлен x^q -x из К[х] вполне разлагается в F[х] следующим образом

x^q -x=(х -а), аF,

так что F является полем разложения многочлена x^q -x над полем К.

На основе представленных лемм можно сформировать главную характеризационную теорему конечных полей.

Теорема о существовании и единственности конечных полей. Для каждого простого числа р и каждого натурального числа n существует конечное поле из рⁿ элементов. Любое конечное поле из q=рⁿ элементов изоморфно полю разложения x^q -x над полем F_p.

Эта теорема позволяет ввести в рассмотрение т.е. построить конкретное конечное поле Галуа порядка q, содержащее q элементов, где q - это степень простого числа р, которое является характеристикой этого поля. Поля этого типа обозначают F_q или GF(q).

Для конечного поля F(q) будем обозначать через F^*(q) мультипликативную группу его ненулевых элементов. Тогда следующая теорема устанавливает важное свойство такой группы.

Теорема. Мультипликативная группа F^*(q) ненулевых элементов произвольного конечного поля F_q является циклической, с образующим элементом b  F_q.

Определение. Образующий элемент b  F_q циклической группы F^*_q называется примитивным элементом поля F_q.

Теорема. Пусть F_q – конечное поле и F_r его конечное расширение. Тогда F_r является простым алгебраическим расширением поля F_q, причем образующим элементом этого простого расширения может служить любой примитивный элемент поля F_r.

Отсюда имеет место важное следствие: Для каждого конечного поля F_q и каждого натурального числа n в кольце F_q[x] существует неприводимый многочлен f(x) степени n.

Рассмотрим теперь вопрос о множестве корней неприводимого многочлена над конечным полем. На этот важный вопрос дают ответ следующие теоремы конечного поля.

Лемма. Пусть f_(x) F_q[x] - неприводимый многочлен степени m над F_q. Тогда f_(x) делит многочлен -x тогда и только тогда, когда число m делит n (т.е. m/n).

Теорема Галуа. Если f_(x) F_q[x] неприводимый многочлен степени m, то в поле F_q^m содержится любой корень, а многочлена f(x). Более того, все корни многочлена f(x) просты (напомним, что корень простой, если его кратность к=1) и ими являются m различных элементов , , ,..., поля F_q^m.

Из этой теоремы следуют следующие факты:

1. 
   Неприводимый многочлен f_(x) F_q[x] над полем F_q^m вполне разлагается в этом поле, т.е. (см. лемму 3). Поле F_q^m является полем разложения над полем F_q.
   
2. 
   Поля разложения любых двух неприводимых многочленов одной и той же степени из кольца F_q[x] изоморфны.
   
3. 
   Каждое конечное расширение F_q^m конечного поля F_q является нормальным расширением, т.е. оно обладает тем свойством, что каждый неприводимый многочлен из F_q[x], имеющий хотя бы один корень в поле F_q^m, разлагается в этом поле на линейные сомножители.
   
4. 
   Любое конечное поле является совершенным полем, т.е. обладает следующим свойством: каждый неприводимый многочлен над этим полем имеет лишь простые корни.
   

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

Определение.Пусть F_q^m расширение поля F_q , и пусть аF_q^m. Тогда элементы , , ,..., называются сопряженными с элементом относительно F_q.

Пусть К=F_q, F_q= F_q^m (т.е конечное расширение F конечного поля K это векторное пространство над K). Тогда размерность F над K равна m, и если {a₁, ..., a_m } базис пространства F над полем K или базис поля F над K, то каждый элемент aF однозначно представим в виде линейной комбинации

a=c₁a₁+...+ c_ma_m, c_jK, .

Тогда можно ввести важную функция из F в K, которая также является линейной.

Определение. Пусть K=F_q, F=F_q^m и aF. Тогда определим след элемента a над равенством

.

Если K простое подполе поля F, то называют абсолютным следом элемента a и обозначают .

Иными словами след элемента а над полем K есть сумма всех сопряженных с а относительно K элементов.

Дадим еще одноопределение следа. Пусть f(x)K[x] минимальный многочлен элемента aF над полем K. Его степень d является делителем числа m. Назовем многочлен g(x)=f(x)^m/d из K[x] характеристическим многочленом элемента а над полем К. Согласно представленной выше теореме Галуа корнями многочлена f(x) в поле F являются элементы , поэтому получаем, что корнями многочлена g(x) в поле F являются элементы, которые сопряжены с элементом а относительно поля K. Отсюда



и сравнение коэффициентов дает .

Этот след всегда является элементом поля К.

Определение. Для aF=F_q^m и K=F_q определим норму N_F/K(a) элемента а над полем К равенством

.

Через свободный член характеристического многочлена элемента а над полем К: .

Определение.Пусть К конечное поле и F его конечное расширение. Тогда два базиса {a₁,...,a_m} и {b₁,...,b_m} поля F над К называется дуальными, если для

.

Определение. Пусть K=F_q и F=F_q^m. Тогда базис поля F над К вида состоящий из подходящим образом выбранного элемента aF и сопряженных с ним относительно поля К элементов, называют нормальным базисом поля F над К.

Пример: Пусть aF₈ корень неприводимого многочлена x³+x²+1 из F²[x]. Тогда {a,a²,(1+a+a²)} - базис поля F₈ над F₂. Однозначно определенным к нему дуальным базисом (в данном случае автодуальным) будет этот же базис. Действительно элемент a⁵F₈можно представить в виде

a⁵=c₁a+c₂a²+c₃(1+a+a²),

где коэффициенты c₁, c₂, c₃из F₂ определяются



так, что a⁵=a²+(1+a+a²).

Указанный базис является также нормальным базисом поля F₈ над F₂, т.к. 1+a+a²=a⁴. Чтобы разобраться в представленном выше примере рассмотрим один из способов представления элементов конечного поля F_q из q=p² элементов. Идея этого способа базируется на следующих фактах: Поле F_q является простым алгебраическим расширением простого поля F_p. Если f(x) неприводимый многочлен степени n из F_p[x] , то любой корень а этого многочлена принадлежит полю F_pⁿ=F_q и потому F_q=F_p(a). Тогда каждый элемент поля F_q можно однозначно представить в виде значения некоторого многочлена от х над F_p степени не более n -1, при x=a.

Например, чтобы представить таким способом элементы поля F₉ будем рассматривать это поле как простое алгебраическое расширение степени 2 поля F₃, которое получается присоединением корня а неприводимого над F₃ многочлена степени 2, пусть это будет f(x)=x²+1F₃[x]. Тогда f(a)=a²+1=0 в F₉ и девять элементов поле F₉ можно задать в виде: p₀+p₁a, где p₀,p₁F₃. Точнее, F₉={0,1,2,a,1+a,2+a,2a,1+2a,2+2a}.

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

У каждого ненулевого многочлена f(x) над конечным полем кроме его степени deg(f(x)) имеется еще одна важная целочисленная характеристика – его порядок.

Лемма. Если f(x)F_q[x] многочлен степени m1, удовлетворяющий условию f(0)0, то существует натуральное число , для которого двучлен x^e -1 делится на f(x).

Этот факт позволяет ввести определение порядка многочлена над конечным полем.

Определение. Пусть f(x)F_q[x] ненулевой многочлен. Если f(0)0, то наименьшее натуральное число е, для которого многочлен f(x) делит (x^e -1) называется порядком многочлена f(x) и обозначается ord(f(x)). Если же f(0)=0, то многочлен f(x) однозначно представим в виде f(x)=x^hg(x) где hN, g(x)F_q[x] и g(0)=0 и тогда ord(f(x)) многочлена f(x) определяется как ord(g(x)).

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

Теорема. Пусть f(x)F_q[x] неприводимый многочлен степени m, удовлетворяющий условию f(0)0. Порядок этого многочлена совпадает с порядком любого корня этого многочлена в мультипликативной группе F* поля F_q^m.

Отсюда вытекает важное следствие: Если f(x)F_q[x] неприводимый многочлен степени m над полем F_q, то его порядок ord(f(x)) делит число q^m -1.

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

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

Лемма. Пусть с – натуральное число. Многочлен f(x)F_q[x], удовлетворяющий условию f(0)0 делит двучлен x^c -1 тогда и только тогда, когда ord(f(x)) делит число с.

Следствие. Если е₁ и е₂ натуральные числа, то НОД многочленов (x^e1 -1) и (x^e2 -1) в F_q[x] равен (x^d -1), где d=НОД(е₁, е₂).

Теорема. Пусть nN и g(x) – неприводимый многочлен над конечным полем характеристики P, такой что g(0)0. Тогда для многочлена вида f(x)=gⁿ(x) имеем

ord(f(x))=ord(gⁿ(x))=p^tord(g(x)),

где t – наименьшее целое число, для которого p^tn.

Теорема. Пусть g₁(x),...,g_k(x) – попарно взаимно простые ненулевые многочлены над полем F_q, и пусть f(x)=g₁(x)g₂(x)...g_K(x), тогда

ord(f(x))=ord(g₁(x))ord(g_K(x))=НОК(ord(g₁(x),...,ord(g_K).

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

Пример: f(x)=x¹⁰+x⁹+x³+x²+1F₂[x].

Каноническое разложение f(x) над полем F₂ имеет вид f(x)=(x²+x+1)³(x⁴+x+1). Т.к. ord(x²+x+1)=3 и имея ord(gⁿ(x)=p^tord(g(x)), получаем, что ord((x²+x+1)³)=2²3=12 т.к. у нас F₂ т.е. p=2 и t=2 чтобы 2²>3). Далее ord(x⁴+x+1)=15. Тогда ord(f(x))=НОК(12,15)=60.

Обобщить эти результаты можно теоремой.

Теорема. Пусть F_q конечное поле характеристики p. Если каноническое разложение в кольце F_q[x] многочлена f(x)F_q[x] положительной степени, такого что f(0)0, то

,

где t – наименьшее целое число, удовлетворяющее неравенству p^tmax{n₁,...,n_K}.

Из определения порядка е многочлена f(x) следует, что е это наименьшее натуральное число, удовлетворяющее сравнению: x^e1(mod(f(x)),

т.к. это сравнение означает, что f(x) делит x^e -1. Отсюда следует еще один способ определения порядка многочленов. Согласно приведенному выше следствию 1 порядок е делит число q^m -1, где m степень многочлена f(x). Предполагая q^m>2 будем исходить из разложения числа q^m -1 на простые сомножители:

.

Для каждого найдем вычеты одночлена по модулю f(x) (т.е. остатки от их деления на f(x)). Обычно это делается перемножением подходящим образом выбранного набора вычетов по модулю f(x) степеней переменной x. При этом, если ,то число е делится на , в противном случае, число е не делится на . В последнем случае мы выясняем, будет ли число е делится на , , ..., , вычисляя соответственно вычеты по модулю f(x) следующих степеней переменной x: , ,..., . Такой подсчет проводится для каждого простого делителя p_j числа q^m -1 и в итоге находится порядок e=ord(f(x)).

В этом методе ключевым моментом является разложение на простые сомножители натурального числа q^m -1. Существуют обширные таблицы для полного такого разложения указанных чисел, особенно для q=2 т.е. для полей F₂ и F₂^m.