Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
200
Часть II. Математические основы
можно разложить на п линейных полиномов. Пока не будем уточнять, в каком именно пространстве лежат его корни.
Обозначим корни уравнения /(х) = 0 через
0o,0i,...,0n-i- (5-4.6)
Поскольку полином /(х) является неприводимым над полем F, эти корни не могут принадлежать полю F.
Теорема 5.7. Пусть F — конечное поле, a f е F[x] — неприводимый полином степени п над полем F. Если в — произвольный корень уравнения /(х) = 0, то элементы
М.е2,...,^-1
линейно независимы над полем F, т.е. для ti € F, где г = 0,1,2,..., п — 1,
г0 + ПА + г2в2 + - - • + rn-iff1-1 = 0 =^ r0 = ri = --- = r„_i=0. (5.4.7)
Доказательство. Пусть в — произвольный корень уравнения /(х) = 0. Известно, что в ф 1, поскольку полином /(х) является неприводимым над полем F, которое содержит единицу. Допустим, что элементы 1, в,в2,..., вп~1 не являются линейно независимыми над полем F. Иначе говоря, линейная комбинация (5.4.7) может равняться нулю при некоторых е F, где г = 0,1,2,..., п — 1, которые не обращаются в нуль одновременно. Это значит, что элемент в является корнем уравнения
г(х) — г0 + т\х + r2x2 Н-----Ь rn_ixn_1 = 0.
Если Ti е F(i = 0,1,2,..., п — 1), то по определению 5.21 полином г(х) принадлежит полю F[x]/. Следовательно, условие г(х) = 0 равносильно условию r{x) = 0(mod/(x)). Пусть ап — старший коэффициент полинома /(х). Тогда an€F,an ф 0 и с~1/(х) | г(х). Однако это невозможно, поскольку полином a~lf(x) имеет степень п, в то время как степень полинома г(х) меньше п. Следовательно, полином г(х) является нулевым. Это противоречит сделанному предположению о том, что не все е F(i = 0,1,2,..., ?г — 1) равны нулю. ?
Определение 5.22 (Полиномиальный базис). Пусть F — конечное поле, а /(х) — неприводимый полином степени п над полем F. Тогда для любого корня в уравнения /(х) = 0 элементы 1, в,в2,..., вп~1 называются полиномиальным базисом конечного векторного пространства над полем F.
Как известно из курса линейной алгебры, базис, состоящий из п элементов, порождает n-мерное векторное пространство. Для этого используются скалярные
ва 5. Алгебраические основы
201
целичины, принадлежащие полю F, т.е. векторное пространство, порожденное •азисом 1,в,в2,...,071-1, имеет следующую структуру
{п-1 i=0
го,Г1,--.,гп_1 G F
)
(5.4.8)
Теорема 5.8. Пусть F — конечное поле, a f(x) — неприводимый полином степени п над полем F. Тогда для любого корня в уравнения /(ж) = 0 векторное пространство (5.4.8) является конечным полем и состоит из (j?F)n элементов.
Доказательство. Во-первых, покажем, что векторное пространство (5.4.8) является кольцом. Единственный нетривиальный момент в этом доказательстве заключается в проверке аксиомы замкнутости. Для этого отметим, что уравнение
f(9) = anff1 + ап-19п-1 + ... + ао = 0, где an е F капф 0, можно переписать в следующем виде:
(5.4.9)
Г = a'1 {-On-yt
ао
Таким образом, вп является линейной комбинацией элементов базиса 1,в,92,..., в71-1. Умножая 9 на выражение (5.4.9), легко показать, что для любого положительного целого числа т ^ п, элемент 9т можно представить в виде линейной комбинации элементов того же самого базиса. Следовательно, для любых элементов и, v из пространства (5.4.8) произведение uv, будучи линейной комбинацией базисных элементов 1,в,92,...,вт при т ^ 2(п — 1), должно быть линейной комбинацией базисных элементов l,^,^2,...,^71-1, т.е. принадлежит пространству (5.4.8). Итак, аксиома замкнутости выполняется.
Во-вторых, для того, чтобы показать, что пространство (5.4.8) является полем, необходимо показать, что оно не содержит нулевых делителей. Для этого можно применить условие линейной независимости (5.4.7) и убедиться, что из условия uv = 0 следует равенство нулю одного из двух скаляров и и v.
В заключение отметим, что в разложении элементов пространства по базису используются #F скаляров из поля F, а сам базис состоит из п элементов. Следовательно, пространство (5.4.7) состоит из (#F)n элементов. ?
Определение 5.23 (Конечное поле Fqn). Пусть q — количество элементов конечного поля F. Символом ?дп обозначается конечное поле, построенное по базису, состоящему из п элементов над полем F.
Теорема 5.9. Пусть F — конечное поле, состоящее из q элементов, a Fg« — конечное поле, построенное по базису поля F. Тогда
202
Часть II. Математические основы
1) характеристики полей Fgn и F совпадают,
2) поле F является подполем поля Fgn,
3) любой элемент а 6 Fgn удовлетворяет условию aq = а тогда и только тогда, когда а€ F.
Доказательство. Пусть 1, в, в2,..., вп~г — базис поля Fgn над полем F.
1. Обозначим характеристику поля F через char(F). Тогда, складывая любой элемент поля Fgn с самим собой char(F) раз, получаем
71—1 П—1
chartF)^ = ^ 00* = 0.
г=0 i=0
Следовательно, char(Fgn) = char(F).
2. Поскольку базис содержит единицу, то, используя скалярные величины из поля F, любой элемент поля F можно представить в виде линейной комбинации единицы, т.е. в виде линейной комбинации элементов базиса.
3. (<=). Рассмотрим подполе F = {0}UF*, где F* — мультипликативная группа ненулевых элементов. Тогда из условия а € F следует, что либо а = 0, либо a G F*. Для первого варианта условие aq = а является тривиальным. Для второго варианта по теореме Лагранжа (следствие 5.2) ord(a) | #F* = о — 1, и, следовательно, ач~1 = 1. Таким образом, ад = а.
