Полагая

(пр-\-А

для любых 0:Л <<риОД <.Р-

На основании этого факта доказательство теоремы легко завершается прямым применением индукции по /.

Замечание. Теорема не верна для непростых р. Например, (J2) = 1 mod 10, но (J) (2) = 6 mod 10;

(2) =2 mod4, но (J) (°)=0mod4.

4.72. Следствие. j=0 mod p, за исключением того случая, когда Ki Ni для всех i.

4.73. Пример. Предположим, что w - элемент из GF (2) с минимальным многочленом М (х) = + + + 1. Каков минимальный многочлен элемента и; + 1?

Ответ. Работая по модулю два, получаем:

1011 1010 1001 1000 111 110 101 100 И 10 1 О (а;+1)1011= 1 1 1 1 00001111 (а; 1 1)1000 = 1 1

(a; + l)iei= 11 11

(х+1)"= 1 1

1= 1

1 1 1 0 0 0 1 1 1

G(a;)=--x" f x" + a;9 + x5 + a;* + a;Hl•

0 О 1

Часто встречается такая ситуация, когда известен минимальный многочлен М<-) (х) элемента а и надо определить минимальный многочлен M) (х) элемент а. Для некоторых значений к многочлен (х) определяется сравнительно просто. В частности, если порядок а равен пш к сравнимо со степенью характеристики по модулю п, то МЧ (х) = (х). Другой простой случай - это когда число - А; сравнимо со степенью характеристики по модулю п; тогда МС) (х) = (ж). Если (х) = J\Ml"x\ то (х) =

= 2 -m-i- Вообще {х) может быть получен с помощью

обращения (выписывания в обратном порядке) коэффициентов

Существуют также методы, позволяющие определить МС) (х) по MW (х) для других значений к. Такие методы были описаны Дэйкином [1965], Голомбом [1967] и другими. В качестве примера таких методов рассмотрим определение М (х) в поле характеристики 2 по заданному М) (х). Так как корни М<-) (х) являются кубами корней М() (х), то M) (х) должен делить Л/*) (х). Аналогично, если д - примитивный кубический корень из единицы {д е GF (4)), то (дх) и М() {дН) также должны делить Ж) {з?). С другой стороны, каждый корень многочлена (а?) является

корнем либо Af() (х), либо М() {дх), либо {дх). Следовательно,

4.74. Теорема. Многочлен M()(a:)M()(5a;)M()() является степенью многочлена М*) {з?).

Зная (х), можно вычислить М<){х)МС){дх)М<){дЪ). Так

как 5 = 1, то многочлен Af() {дх) может быть представлен в виде квадратного многочлена от д, коэффициентами которого являются многочлены от х.

МЦдх)==А-{-Вд + Сд\

где А=--А{з), В = хВ{з?), С = хЮ{х).

{х) М<" {дх) М<1> (5%) = = {А + В-С){А + Вд-\- Сд) {А + Вд + Сд) = = АВС + А + ВС.

Например, пусть необходимо определить Af(a;) при Л/(а:) = = x-\--x-{-x-\-x->r\. Тогда Л=-1 + а;в; 5 = а; + а:*; С = а:2. Следуя Голомбу [1967], вычисления будем производить с помощью таблицы 4.2, выписывая только показатели степеней ненулевых членов

Таблица 4.2

Кубическое преобразование многочлена

а5в + ж*--ж2--ж+1

I 1=0 при А<В, получим, что (1 + 5)0(5)°°

многочлена. Начнем с записи в столбце А показателей членов многочлена Afi(3r), которые =0mod3, в столбце 5- показателей, которые =lmod3, в столбце С - показателей, которые =2mod3. Затем найдем члены вида (смешанные) в выражении А.

В обш,ем случае Л = 2 Aix и = ( Aixf = (2 Atx) (2 Ajxf =

- (S Aix) (2 Ajxi) = 2 AiX + AtAjxK

i 3 i гфЗ

Смешанные члены имеют вид xi, так как при i Ф j Ai = Aj = i. В рассматриваемом примере смешанные члены дают: О + 2-6 = = 12и6 + 2.0 = 6. Деля эти кубические смешанные члены на 3, мы получаем 4 и 2, приведенные в таблице. Аналогично мы подсчитываем кубические смешанные члены для В. Это 1 + 2-4 = 9 и 4 + 2-1 =6. Деля эти кубические смешанные члены на 3, получаем 3 и 2, приведенные в таблице. Наконец, найдем члены произведения ABC. В данном примере таких членов четыре: О + 1 + 2 = = 3;0 + 4 + 2 = 6;6 + 1-Ь2 = 9и6 + 4 + 2 = 12. Их деление на 3 дает числа 1, 2, 3 и 4, приведенные в таблице. Произведя суммирование но столбцам и учитывая подобные члены, получаем О, 4, 6. Значит, М<){х) М<){дх) М<)(дх) = 1 + (х)* + (х, так что 1 + х* + х" - степень многочлена (х). Так как М{х)

неприводим, то М)(х) = I + х + х.

Практически многочлен Mi{x) M<-i{dx) М<->{дх) обычно оказывается равным первой степени МЦа?). Это справедливо всегда, если 7lf(i)(a;) имеет четную степень, и обычно получается в других случаях. Однако, как показывает рассмотренный пример, может

Таблица 4.3 Кубическое преобразование многочленов

случиться, что 7lf(i)(a;) 7lf(i)(5a;) М(дх) является квадратом многочлена МЦх).

В качестве последнего примера вычислим минимальные многочлены всех элементов ноля GF (2°), если МЦх) = i + х -\- х. В таблице 4.3 выписаны результаты вычисления Ml (х). Повторяя преобразование, вычисляем затем Af() (х). Зная M->{x), М-1{х) и М() (х), тривиальным образом вычисляем Af(~i)(x), М-~Цх) и M-l (х). Это дает все неприводимые двоичные многочлены пятой степени, приведенные в таблице 4.4. Аналогичные методы могут

Таблица 4.4

Минимальные многочлены элементов поля GF{2)

Циклические сдвиги двоичной записи показателей

быть использованы для нахождения М>{х) непосредственно но М() (х); отправной точкой при этом служит то, что Af<*>(a;) является корнем многочлена

Л/"1> (х) Л/<1> (Ix) Л/"< 1> Цх) М<1 (ga;) Tlf CD Цх),

где I - примитивный корень из единицы пятой степени. Подобным же образом могут быть найдены M-Цх), .... Хотя рассмотренная техника особенно полезна при ручных подсчетах многочленов относительно малой степени, она обычно облегчает и машинное вычисление многочленов большей степени с помощью методов, описанных выше.

Задачи

4.1. (Лехмер [1936]). Доказать следующие утверждения относительно коэффициентов (3") круговых многочленов

ф(п) i=0

(а) Если п равно произведению двух различных простых чисел, то (?" равны О или 1 при всех i.

(b) Если п < 105, то 1 I равны О или 1 для всех i.

(c) Для произвольного заданного числа А существуют такие rent, что

Указание. Пусть " = J Pj, где А -\- i а pj - различные простые числа, 3=1

такие, что pf/2 < pi < < • • • < Рг- Показать, что (?р" = 1 - t.

(d) Для любого заданного числа А существуют такие простые числа р, q ж г, что 1 Q- 1 ;> А для всех 1.

Указание. Для данного р > 2А теорема Дирихле гарантирует существование таких g и г, что q = 2 mod р, 2г = - 1 mod pq. Показать, что

Q\% (,r+l)/2 = (Р - 1)/2-

4.2. Пусть примитивный элемент а поля GF (22»п) является корнем много -члена il/<*> {х). Определить минимальный многочлен а над GF (2) и над GF (2"») в каждом из следующих случаев:

(a) 2т. = 6, (х) = я» + я + 1.

(b) 2т = 8, Ж<1) (х) = х8 4 J.3 Д.2 1.

(c) 2го = 10, il/a)(x) = а;10 а-з 1.

4.3. Так же, как в задаче 4.2, для m = 3, 4, 5 и каждого \GF (2т) найти такое число п (), что а + g = а". Найти такие числа i () и / (), что

а + I = piyi, где р = «2"+! и Y = а"--

4.4. Показать, что умножение и деление произвольных элементов поля GF (22т) вида Аа, В, АВ GF (2">) может быть сведено к сложению и вычитанию чисел по модулю 2"» ± 1 с помощью четырех таблиц, содержащих не более 2"» элементэв.

Указание. Если Л О, то Аа -\- В = А (а -\- В/А).

4.5 (Берлекэмп [1968с]). Пусть q - степень простого числа, т - простое

число, а - примитивный элемент поля GF (gm). Пусть Тг (х)= .Для 1

каждого элемента i GF (q) положим

55 = {ft I О < ft < < fern 1) и Тг (а») = }.

Ясно, что и 55={0, 1, 2, . . ., г iqm - 1) - 1}. Показать, что для каждого § множество содержит арифметическую прогрессию не более чем из t членов.

4.6. Пусть Л" (а:) = 2 "" = 0.

Л(1) = Л(2) = 1, Л<з>=1+х, Л(4) = 1-)-2а;, = 1-j-3i + x2, Л<б) = 1-[-4х+Зх2.....

Доказать следующие утверждения:

(a) Rin+i) = Л(п) -- хЛ<п-1).

(b) Л<п+т) = Д(т+1)Д(п) -j- хЛ(т)Д<п-1).

(c) Если d I и, то Л<Л 1 Л<п).

(d) Если / (х) - неприводимый многочлен и / 1 R<d) но / t Л<*> для любого i <С d, то / t Л<п, за исключением случая, когда d п.

(e) Если d = н. о. д. (ге, т), то н. о. д. (Л<п), Л(т)) fl<d,,

(f) Л(2гЧ-1) = [Л(п+1)]2 [Л(П)]2

(g) Д<2п) = [Л(п)]2 2хЛ(")Л(п-1).

(h) Над полем GF (2): Л" = 1; л<2«+1)= x-i fl(20 i)j j "у .г

fe=o

(i) Над полем GF (2): если / (х) - нерриводимый многочлен, / 1 Л*") , но / 1 Л<<> для любого j < ге, то степень / (х) равна d, где d - наименьшее из чисел ,7, таких, что 23 = + 1 mod п.

б/- (2)? значений п £ 20 многочлен i?(2n+i) () неприводим над

(к) Используя теорему Лукаса, выписать ROoiy () как двоичный многочлен степени 50.