А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии (1127102), страница 17

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

Текст из файла (страница 17)

□

Для кольца с разложением на простые множители есть простой критерий, когда оно является факториальным. Доказательство критерия можно посмотреть, например, в учебнике А.И. Кострикина Введение в алгебру.

Теорема. (Критерий факториальности)

Если кольцо имеет разложение на простые множители, то оно факториально тогда и только тогда, когда для любого простого элемента p из того, что p\(ab) следует, что p\a или p\b.

Критерий кажется очевидным и даже несколько наивным. Однако, если Петю (p) смогли поднять вдвоем Антон (a) и Борис (b) не обязательно, что это они смогут сделать по отдельности.

Теорема (факториальность евклидовых колец).

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

Доказательство.

Применим критерий факториальности. Пусть простой элемент p делит произведение ab, но не делит элемент a. Так как элемент p простой, то НОД(p,a) = 1 и, значит, в силу алгоритма Эвклида найдутся элементы такие, что ua+vp=1. Умножая это равенство почленно на элемент b, получаем uab+vpb=b. Так как оба слагаемых в левой части равенства делятся на элемент p, то и правая часть делится на p. Значит p\b. Если элемент p не делит b, то аналогично получим, что p\a.

□

Следствие. В евклидовом кольце число простых элементов бесконечно. В частности, бесконечно число простых чисел и неприводимых многочленов.

Идея использовать метод Евклида для получения новых простых чисел не безнадежна, но мало эффективна. Начнем с первых трех простых чисел 2, 3, 5. Далее получаем , имея четыре числа 2, 3, 5, 31 получим . Вновь появляющиеся числа не только не обязаны быть простыми, но даже и не обязательно дают простые множители, превосходящие предыдущие.

§2. Конечные поля и неприводимые многочлены.

Конечным полем является построенное нам выше кольцо вычетов по простому модулю Z_p. В честь великого французского математика Эвариста Галуа (1811 - 1831) конечные поля называют полями Галуа и обозначают GF(q), где q – порядок поля.

Нас интересует, что это за число q, можно ли построить два разных (неизоморфных поля), которые имеют одно и тоже число элементов. А главное как поля Галуа задавать на практике и как производить в них вычисления.

Основные понятия алгебры мы упомянем кратко, все же наша цель - криптография и теория чисел. Так что мы не будем определять векторное пространство, подпространство, базис и размерность.

Определение. Подмножество L поля P называется подполем, если оно является полем, относительно операций, заданных в поле P. Записывается этот факт стандартно .

Если в поле P выделить как главную операцию, операцию сложения, а умножение на элементы из L рассматривать как действие поля на абелеву группу, то мы увидим, что P – векторное пространство над полем L.

Определение. Размерность векторного пространства P над полем L называется степенью расширения поля P над полем L и обозначается

Теорема (О башне полей).

Если имеется цепочка конечных расширений полей P > L > K, то степень итогового расширения равно произведению степеней промежуточных расширений .

Доказательство.

Если базисные элементы векторного пространства P над L умножить поэлементно на базисные элементы пространства L над K, то получится требуемый базис. Это нужно проверить или самому или посмотреть в любой книжке по теории полей.

Теорема (вторая теорема о полях Галуа).

Каждое конечное поле содержит в качестве подполя некоторое поле вычетов GF(p) и поэтому имеет порядок вида pⁿ , для подходящего натурального числа n.

(Таким образом, ответ на один из вопросов получен – число элементов в конечном поле всегда является степенью простого числа. Уже теперь можно утверждать, что полей порядка 6 или 82 не существует.)

Доказательство.

а) Пусть Р – конечное поле и e – его нейтральный элемент по умножению. Рассмотрим суммы нейтрального элемента самого с собой: e, e+e, e+e+e, … Т.к. поле конечное, то суммы начнут повторяться, например, ne=me, n<m. Вычитая их друг из друга получаем, что (m—n)e=0. Покажем, что на самом деле число m–n является простым (оно называется характеристикой поля). Если бы это число было составным, то мы, по определению нейтрального элемента по умножению, получили бы . Т.к. в поле нет делителей нуля, то или ke=0 или le=0. Если опять k или l - составное число, повторяем процедуру вновь.

б) Итак, для некоторого простого числа p, в поле P содержится полугруппа по сложению, состоящая из элементов {e, 2e, 3e, …, (p-1)e, 0}. Остается проверить, что эта полугруппа изоморфна полю вычетов Z_p={1,2,3,…,p-1,0}. Как задается изоморфизм совершенно очевидно, элемент ke переходит в элемент k. Проверка свойств изоморфизма стандартна.

в) Пусть P, как векторное пространство над Z_p, имеет размерность n. Пусть b₁, b₂, …, b_n – базис. Тогда каждый элемент из P может быть записан в виде . А таких записей ровно pⁿ штук. Теорема доказана.

□

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

Определение. Наименьшее натуральное число n, такое, что для любого элемента a кольца К выполняется условие na=a+a+…+a=0 называется характеристикой кольца.

Например, характеристики колец Z₁₄, Z₈[x], M₅(Z₁₂₅) равны 14, 8 и 125 соответственно.

Если поле имеет характеристику p, т.е. сумма любых p элементов равна 0, то в нем верна формула (a+b)^p=a^p+b^p. Дело в том, что по формуле бинома Ньютона все промежуточные биномиальные коэффициенты будут кратны p и, поэтому, все промежуточные слагаемые обнулятся. Эта формула имеет очевидное обобщение .

Наша главная цель показать, что для любой степени pⁿ существует поле Галуа данного порядка. Но для этого придется ввести еще одно важное понятие.

Определение. Пусть f(x) - многочлен над полем P. Поле L>P называется полем разложения многочлена f(x), если все корни многочлена f(x) принадлежат полю L, и оно порождается этими корнями. Т.е. это минимальное поле, содержащее все корни многочлена f(x).

Теорема (О поле разложения).

Для любого поля P и любого многочлена существует поле разложения. С точностью до изоморфизма это поле единственно.

Доказательство

идейно совпадает с доказательством с первой теоремы о полях Галуа. Только простой элемент кольца целых чисел заменяется на простой элемент кольца многочленов. Поскольку оба кольца евклидовы, то рассуждения идентичны.

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

б) После этого вместо остатков от деления на простое число p рассматриваем все остатки от деления на многочлен f(x). Как и в кольце вычетов вводим операции сложения и умножения. Т.е. в качестве результата берем не обычную сумму и произведение, а остаток от деления на многочлен f(x). Как и в случае колец вычетов проверяется, что получается коммутативное кольцо с единицей.

в) Проверим, что любой ненулевой остаток g(x) имеет обратный по умножению. Т.к. степень многочлена g(x) меньше, чем степень многочлена f(x), а он, в свою очередь, неприводим, то НОД(f(x),g(x))=1. Теперь по алгоритму Евклида в кольце P[x] найдутся многочлены u(x), v(x), такие, что u(x)g(x)+v(x)f(x)=1. Отсюда заключаем, что обратным к остатку g(x) является остаток от многочлена u(x).

г) Теперь можно указать элемент, который в построенном поле остатков, обозначим его L, будет корнем многочлена f(x). Конечно – это остаток, равный многочлену “x”.

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

е) Вопрос о единственности кажется очевидным – просто добавили корни, а они-то только от многочлена зависят, и получили единственное поле. Однако вопрос гораздо тоньше, но мы его обсуждать не будем.

□

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

Пример 1. В современном алгоритме шифрования AES, пришедшем в 26.11.2001 на смену DES, используется конечное поле Галуа GF(2⁸). Это поле является расширением самого маленького поля GF(2), которое состоит из двух нейтральных элементов {0,1}. Неприводимый многочлен, с помощью которого оно строится, согласно стандарта США FIPS-197, имеет вид

f(x)=x⁸+x⁴+x³+x+1. Неплохое упражнение вручную проверить, что многочлен неприводим. Пусть g(x)=x⁷+x³+x+1. Этот остаток задает, согласно FIPS-197, байт со следующими битами 10001011. Одно из основных криптографических преобразований алгоритма AES состоит в том, что элемент поля g(x) преобразуется в обратный к нему по умножению g^-1(x).

Воспользуемся алгоритмом Евклида. Нужно найти такие остатки u, v, что ug+vf=1. Составляем табличку деления с остатком

Теперь нужно выразить последний остаток, равный 1, последовательно через все предыдущие остатки, а потом и через f и g. Обратим внимание, что мы работаем в поле характеристики 2, поэтому x=-x, и (a+b)²=a²+b²:

Итак, получилось, , т.е. и, значит, байт 10001011 под действие одного шага алгоритма AES перейдет в байт 11011001.

Потренируйтесь проверяя наш ответ, перемножьте многочлены g и u, а потом найдите остаток от деления на многочлен f. Остаток должен получиться равным 1.

Теорема (Третья теорема о поле Галуа).

Для любого простого числа p и натурального числа n существует единственное поле Галуа GF(pⁿ), которое является полем разложения многочлена .

Доказательство.

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

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

Теперь проверим, что корни образуют в поле разложения подполе, а, значит, совпадают с полем разложения, ведь оно минимальное поле, содержащее все корни.

Характеристики

Список файлов книги