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

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

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

Пусть a и b – корни нашего многочлена. Нужно проверить, что тогда a+b, ab, -a, a^-1, а также 0 и 1, тоже являются корнями многочлена. Для 0 и 1 это очевидно. Далее, по предположению имеем поэтому, не забывая, что характеристика равна p, получаем

□

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

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

Теорема (О примитивном элементе).

Любое конечное поле имеет примитивный элемент.

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

Мы изложим только идею доказательства. Примитивный элемент, если он существует, должен иметь порядок k=pⁿ–1. т.к. именно столько ненулевых элементов в поле GF(pⁿ). Если же примитивного элемента нет, то все ненулевые элементы поля имеют порядки меньшие числа k. Точнее, их порядки должны делить это число, по теореме Лагранжа. И если S=НОК(порядков ненулевых элементов поля) и S<k, то получится, что многочлен x^S–1 имеет k корней, что невозможно. Если же S=k=pⁿ–1, то можно сконструировать требуемый примитивный элемент.

Идея конструкции такова. Пусть p₁, p₂,…, p_t - все различные простые делители числа k. По предположению, для каждого многочлена должен найтись элемент поля, который не является его корнем. Пусть это будет элемент a_i.

Число k, по основной теореме арифметики, имеет некоторое разложение

. Введем в игру элементы . Произведением этих элементов и является наш примитивный элемент.

□

При выполнении вычислений в конечных полях часто оказывается полезен так называемый логарифм Якоби. Если рассмотреть все ненулевые элементы конечного поля, содержащего q элементов, как степени примитивного элемента b, то операция умножения у нас становится простым сложением по модулю q-1, поскольку .

При использовании примитивных элементов в операциях сложения возникает проблема, как вычислить степень примитивного элемента, равную сумме 1+bⁱ. Это важно, так как

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

Кроме того, для bⁱ =q-1 логарифм Якоби неопределен, т.к. в этом случае bⁱ+1=0.

Пример 2. Вычислим логарифм Якоби в расширении поля GF(3) степени 2. Пусть x²+1 будет тем многочленом, чье поле разложения мы ищем. Данное поле имеет обозначение GF(9), т.е. содержит 9 элементов.

Самое сложное - найти примитивный элемент. Из теории, которая будет изложена позже, в поле GF(9) их ровно , т.е. половина. Напомним, что φ(n) – функция Эйлера, равная количеству натуральных чисел, меньших n и взаимно-простых с n. Для малых конечных полей вполне может подойти либо остаток x, либо x+1. Претендента на примитивный элемент нужно будет возвести в 4-ю степень. Если она окажется неединичной, то это он – примитивный элемент.

Так как x² + 1 = 0, то x² = 2, поэтому последовательно получаем

x, x² = 2, x⁴ = 2² = 1;

x+1, (x+1)² =x²+2x+1=2+2x+1=2x, (x+1)⁴=(2x)²=x²=2.

Таким образом, b=x+1 - примитивный элемент. Составляем таблицу из степеней элемента b, из нее таблица логарифма Якоби получается мгновенно

Теперь рассматриваем суммы 1+bⁱ и находим по таблице, каким степеням a^j они равны. Например, 1+b=x+2=b⁷, т.е. L(1) = 7.

Таблица логарифма Якоби
i	1	2	3	4	5	6	7	8
L(i)	7	3	5	8	2	1	6	4

Аналогично простым числам огромную роль в криптографии играют неприводимые многочлены – простые элементы кольца многочленов. С неприводимыми многочленами ситуация несколько проще, чем с простым числами, по крайней мере можно построить неприводимый многочлен любой степени. В то время как самое большое простое число, известное на 12.09.07 равно 2^32582657-1 – это 44-е простое число Мерсенна.

Заинтересовавшиеся вопросом или желающие принять участие в распределенных вычислениях по получению нового рекордного числа, могут обратиться на сайт http://primes.utm.edu, посвященный этому вопросу.

Теорема (Критерий Эйзенштейна).

Пусть K – кольцо с однозначным разложением на простые множители, например, кольцо целых чисел, f(x)=xⁿ+a_n-1x^n-1+ … +a₁x+a₀ - многочлен над этим кольцом.

Если найдется простой элемент p кольца K, т.е. простое число в случае кольца целых чисел, который делит все коэффициенты a₀, a₁, …, a_n-1, но при этом p² не делит свободный член a₀, то многочлен f(x) неприводим.

Эйзенштейн Фединант Готхольд Макс (1823-1852) ученик К.Ф.Гаусса предложил этот критерий более 150 лет назад. Удивительно, но никаких более сильных критериев неприводимости до сих пор не найдено.

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

Рассмотрим кольцо вычетов по модулю p, тому самому, который делит все коэффициенты. Так как p – простой элемент, то кольцо вычетов на самом деле будет полем, обозначим его P. Многочлен f(x) над полем P примет вид xⁿ.

Пусть многочлен f(x) приводим, и f(x)=g(x)h(x) - его разложение,

g(x)=x^m+b_m-1x^m-1 + … + b₁x+b₀, h(x)=x^k+c_n-1x^k-1+ … + c₁x+c₀, m+k=n.

Пусть над полем P многочлены g(x) и h(x) имеют вид G(x), H(x). Тогда в кольце многочленов P[x] мы получим два разложения xⁿ=G(x)H(x). В силу факториальности кольца P[x] получаем, что G(x)=x^m, F(x)=x^k. Следовательно, у многочленов g(x) и h(x) над исходным кольцом K свободные члены b₀ и c₀ делятся на простой элемент p. А значит, a₀=b₀c₀ делится на p². Противоречие с условием критерия.

□

§3. Кольца многочленов.

3.1. Кольца многочленов.

В предыдущей главе мы подробно рассмотрели кольца Z_m и поля Z^*_p , элементами которых являлись целые числа. Выяснили, что Z_p^* является циклической группой относительно умножения, а также заметили, что любое конечное поле размерности p изоморфно Z^*_p для подходящего p.

Рассмотрим произвольный многочлен степени k с коэффициентами из Z_m:

f(x) = a_kx^k + … + a₁x + a₀.

Степень многочлена будем обозначать как deg f(x).

В силу того, что Z_m – коммутативное кольцо, множество всех многочленов с коэффициентами из Z_m также образуют коммутативное кольцо Z_m[x] вместе с операциями сложения и умножения многочленов. Операция сложения многочленов f(x) = a_kx^k + … + a₁x + a₀ и g(x)=b_kx^k + … + b₁x+b₀ задается как

f(x)+g(x) = (a_k+b_k mod m) x^k + … + (a₁+b₁ mod m) x + (a₀+b₀ mod m),

умножение как

f(x)g(x) = (a_kb_k mod m) x^2k +(a_k-1b_k+a_kb_k-1 mod m)x^2k-1 … + (a₁b₀+a₀b₁ mod m) x + +(a₀b₀ mod m),

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

Пример 1.

Рассмотрим Z₂[x]. Это множество состоит из всех многочленов с коэффициентами из {0,1}. Возьмем два многочлена из Z₂[x]:

f(x) = x⁴+x²+1,

g(x) = x⁴+x³+x+1.

Вычислим сумму и произведение этих многочленов.

f(x)+g(x) = (1+1 mod 2)x⁴ + (1+0 mod 2)x³ + (0+1 mod 2)x² + (1+0mod 2)x + + (1+1 mod 2) = x³+x²+x.

f(x)g(x) = (x⁴+x²+1)(x⁴+x³+x+1) = x⁸ + x⁷ + (2 mod 2)x⁵ + (2 mod 2) x⁴ + x⁶ + (2 mod 2) x³ + x² + x + 1 = x⁸ + x⁷ + x⁶ + x² + x + 1.

Многочлен из Z_m[x] называется неприводимым над Z_m, если его нельзя представить в виде произведения каких-либо двух многочленов из Z_m[x]. Понятие неприводимого многочлена в кольце многочленов эквивалентно понятию простого числа в кольце целых чисел.

Так же как и для кольца целых чисел, для колец полиномов справедлива

Теорема (о делении с остатком)

единственная пара многочленов

0 ≤ deg r(x) < deg g(x): f(x)=g(x)q(x)+r(x).

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

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