Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Определение 5.17 (Поле ?р). Пусть р — простое число. Символом ?р обозначается конечное поле Zp.
Пусть F — произвольное конечное поле простого порядка р. Поскольку существует изоморфизм из F на ?р, любое конечное поле порядка р изоморфно полю ?р. Так как изоморфные поля отождествляются, любое конечное поле порядка р можно называть полем ?р.
Пусть А — конечная алгебраическая структура с операцией сложения +, а символом а обозначен произвольный ненулевой элемент А. Рассмотрим следующую последовательность.
а, 2а = а + а, За = а + а + а,... (5.4.1)
Поскольку А — конечная структура, элемент а имеет конечный порядок, и, следовательно, в последовательности (5.4.1) должна существовать пара чисел (ia,ja) при г < j, где г и j — целые числа, такие что ja — га = (j — г)а = О.
Глава 5. Алгебраические основы
193
Определение 5.18 (Характеристика алгебраической структуры). Характеристика алгебраической структуры А, обозначаемая char(A), — это наименьшее положительное целое число п, такое что па = О для любого элемента a G А. Если такого целого числа не существует, характеристика структуры А равна нулю.
Теорема 5.4. Характеристика любого конечного поля является простым числом.
Доказательство. Пусть F — конечное поле и a G А — произвольный ненулевой элемент. Для последовательности (5.4.1) выполняются соотношения (j — г)а = О и j > г. Следовательно, поле F имеет положительную характеристику. Обозначим ее через п. Поскольку поле F содержит как минимум два элемента (нуль и единицу)» п~^2. Если число п > 2 — не простое, его можно представить в виде п = kl, где k, ? е Z, 1 < к, ? < п. Следовательно,
О = nl = (к?)1 = (к?)11 = (kl)?l.
Отсюда следует, что либо kl = О, либо ?1 — О, поскольку ненулевые элементы поля F образуют мультипликативную группу, не содержащую нулевого элемента О. Значит, либо kal = (kl)a = 0 для всех аЕ F, либо ?al = (?1)а = О для всех oEF. Это противоречит определению характеристики п. ?
5.4.2 Конечные поля неприводимых полиномов
Порядок простого конечного поля равен характеристике этого поля. Однако простое поле нельзя назвать типичным. Более общий вид конечных полей можно создать с помощью полиномов.
5.4.2.1 Полиномы над алгебраической структурой
В главе 4 мы использовали полиномы над множеством целых чисел. Рассмотрим теперь полиномы над абстрактной алгебраической структурой.
Определение 5.19 (Полиномы над алгебраической структурой). Пусть А — алгебраическая структура с операциями сложения и умножения. Полиномом над структурой А называется выражение
п i=0
где п — неотрицательное целое число, коэффициенты ai, 0 ^ г ^ п — элементы структуры А ах — символ, не принадлежащий структуре А. Коэффициент ап называется старшим и не является нулевым элементом структуры А при п ф 0 Целое число п называется степенью полинома f(x) и обозначается как
194 Часть II. Математические основы
f(x)g(x) = ckxk, где ck = ]P аД-. (5.4.3)
fc=0 t+j=fc
0<i^n
Очевидно, что если A — кольцо, то А[х] — тоже кольцо, причем структура Д является подкольцом кольца А[х]. Сложение и умножение полиномов над кольцом! имеют следующие свойства.
deg(J + g) < max(deg(/), deg(p)), deg(/e) < deg(/) + deg(o).
Если A — поле, то, поскольку оно не содержит нулевых делителей, сп+т =1 = a-nbm ф О при ап Ф О и Ьт ф О. Следовательно, в этом случае
deg(/ + g) = deg(/) + deg(p).
Пусть / g € A[x], причем g ф 0. Аналогично делению целых чисел (раздел 4.3.2.1) можно записать
/ = 94 + г» где г е -4[х] и deg(r) < deg(c). (5.4.4)
п = deg(/(x)) = deg(/). Если старший коэффициент равен а®, полином f называется константой. Если старший элемент равен clq = 0, полином f называется нулевым и обозначается как / = 0. Множество всех полиномов над алгебраической структурой А обозначается через А[х].
Если f,g G А[х], где
П ТП
/0*0 = Ylaixl и в(х) = ^2ыхг,
г—0 г=0
ТО
max(n,m) ai + h, г = 0,1,..., min(n, m),
/0е) + в(х) = Qa:*' где с* = < а*, г = m +1,..., n,
1=0 (bi, i = n+l,...,m,
(5.4.2)
и
n+m
Глава 5. Алгебраические основы 195
Пример 5.15. Рассмотрим полиномы /(ж) = х5+х4+х3+х2+х+1е?2[х],д{х) = = х3+х+1е?2[х]. Вычислим полиномы q, геРгМ с помощью деления столбиком.
X2 + X
х3 + X + 1 | ж5 + ж4 + ж3 4- ж2 + ж + 1 ж5 + ж3 + ж2
^4
ж4 + ж + 1
ж4 + ж2 + x
ж2 +~Т
Следовательно, g = ж2 + ж и г = ж2 + 1. ?
Определение 5.20 (Неприводимый полином). Пусть А —алгебраическая структура. Полином f € А[х] называется неприводимым над структурой А (или неприводимым в множестве А[х], или простым в множестве А[х]). если он имеет положительную степень и из равенства f = gh, где g,h? Л [ж], следует, что либо полином д, либо полином h является константой. Полином называется приводимым над структурой А, если он не является неприводимым над ней.
Приводимость полинома зависит от алгебраической структуры, на которой он определен. Полином может оказаться приводимым над одной структурой и непри-1 водимым над другой.
Пример 5.16. Рассмотрим квадратичный полином /(ж) = ж2 — 2ж + 2.
1. Является ли он приводимым над обычными бесконечными алгебраическими структурами?
