Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
2. Является ли он приводимым над конечными полями ?р, где р — нечетное простое число?
3. Разложите полином /(ж) на простые множители над полем ?р при р < 10. Используя формулы элементарной алгебры, вычислим два корня уравнения
/(х) = 0:
а = 1 + y/-L,(3= 1 - л/-1.
1. Поскольку л/—1 не является действительным числом, полином /(ж) оказывается неприводимым над полем R (а значит, и над полями Z или Q). Однако, так как у/—1 = г € С, полином /(ж) является приводимым над полем С.
/(ж) = (ж-1-г)(ж-1 + г).
2. Полином /(ж) является приводимым над полем ?р при любом нечетном простом р тогда и только тогда, когда число л/—Т принадлежит полю Fp, т.е. число —1 является квадратом по модулю р.
-
196
Часть II. Математические основы
Число х является квадратом по модулю р тогда и только тогда, когда существует число ?/(modp), удовлетворяющее условию у2 = x(modp). По малой теореме Ферма (теорема 6.10 из раздела 6.4) все числа x(modp) удовлетворяют условию xp~l = l(modp). Для нечетного простого числа р малая теорема Ферма означает, что
х^ = ±l(modp) (5.4.5)
для всех 0 < х < р, где число —1 означает число р — 1. Если число х является квадратом по модулю р, то условие (5.4.5) принимает следующий вид.
х^ = (г/2)^~ = yv~l = l(modp).
Таким образом, условие (5.4.5) является критерием проверки, является ли число х является квадратом по нечетному простому модулю р: число х — квадрат (соответственно не квадрат) по модулю р, если х * = lmodp (соответственно х г = — 1 modp).
Итак, для любого нечетного простого числа р полином /(х) является приводимым над полем Fp тогда и только тогда, когда (—1) 2 = 1 mod р, и неприводимым, когда (—1) 2 = —1 modp. Иначе говоря, полином /(х) является приводимым (или неприводимым) над полем Fp, если р = l(mod4) (или p = 3(mod4)).
3. При р = 2 полином /(х) = х2 — 2х + 2 = х2 — Ох + 0 = х2 является приводимым над полиномом F2.
Единственное нечетное простое число, которое меньше 10 и сравнимо с 1 по модулю 4, равно 5. Поскольку —1 = 4 = 22(mod 5), т.е. \f—l = 2(mod 5), полином /(х) можно разложить на множители над полем F5.
/(х) = (х - 1 - \/-Г)(х - 1 + V^l) = (х - 1 - 2)(х - 1 + 2) = (х + 2)(х + 1).
Второй квадратный корень числа —1 в поле F5 равен 3. Читатели могут самостоятельно убедиться, что при этом получается точно такое же разложение полинома! /(х) над полем F5. ?
5.4.2.2 Построение поля с помощью неприводимых полиномов
Построим конечное поле с помощью неприводимого полинома.
Определение 5.21 (Множество А[х] по модулю полинома). Пусть А — алгебраическая структура, а полиномы /,g,q,r € А[х], где g ф 0, удовлетворяют^ условию (5.4.4). Тогда полином г называется остатком от деления полинома f на полином д. Этот факт записывается как г = f mod д.
Глава 5. Алгебраические основы
197
Остатки от деления всех полиномов из множества А[х] по модулю g называются полиномами из множества А[х] по модулю д. Множество таких полиномов обозначается как А[х]д.
Множество А[х\/ состоит из всех полиномов, степени которых меньше deg(/).
Теорема 5.5. Пусть F — поле, a f — ненулевой полином из множества F[x\. Тогда множество F[x]f — кольцо и является полем тогда и только тогда, когда полином f неприводим над полем F.
Доказательство. Во-первых, множество ^[ж]/ очевидно является кольцом относительно сложения и умножения по модулю /, определенному соотношениями (5.4.2), (5.4.3) и (5.4.4). Нулем и единицей в этом кольце являются нуль и единица поля F.
Во-вторых, пусть -Р[ж]/ — поле. Допустим, что / = gh, где g и h — полиномы из множества F[x], не являющиеся константами. Тогда, поскольку 0 < deg(g) < deg(/) и 0 < deg(h) < deg(/), полиномы д и h не являются константами в множестве ^[ж]/, несмотря на то, что элемент / является нулевым полиномом в -Р^ж]/. Это противоречит аксиоме замкнутости для мультипликативной группы -^[ж]/. Следовательно, множество F[x]f не может быть полем. Полученное противоречие доказывает, что полином / не может быть приводимым над полем F.
В заключение, пусть полином / является неприводимым над полем F. Поскольку множество F[x]f — кольцо, достаточно показать, что для любого ненулевого элемента множества F[x]f в нем существует элемент, обратный относительно умножения. Пусть г — ненулевой полином из F[x]f, причем gcd(/, г) = с. Поскольку deg(r) < deg(/), а полином / является неприводимым, полином с должен быть константой. Представим полином г в виде г = cs. Тогда с € F, s € F[x] f и gcd(/, s) = 1. Как и в целочисленной арифметике, к полиномам можно применить обобщенный алгоритм Евклида и вычислить s_1(mod/) € ^[ж]/. Кроме того, поскольку с € F, существует элемент с-1 € F. Итак, мы получили элемент г-1 = с-1 в'1 Е F[x]f. ?
Неприводимый полином / называется определяющим полиномом (definition polynomial) конечного поля -Р[ж]/.
Теорема 5.6. Пусть F — поле, состоящее из р элементов, a f — неприводимый полином степени п над полем F. Тогда количество элементов поля F\x\j равно р™.
Доказательство. Из определения 5.21 следует, что ^[ж] f — множество всех полиномов из множества -^[ж], степень которых меньше deg(/) = п, а коэффициенты принадлежат полю F, состоящему из р элементов. В поле -^[ж]^ существует ровно р71 таких элементов. ?
