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

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

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

Мы изложим только идею доказательства. Примитивный элемент, если он существует, должен иметь порядок 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.

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

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