Решение. Найдем матрицу (2, строками которой являются четные степени х, редуцированные но модулю g (х). Это дает

Так как нуль-подпространство матрицы - J состоит из 1 то g [х) - степень неприводимого многочлена. Так как многочле g (ж) = ж + 1 не имеет обш;их делителей с g {х), то g (ж) -ненрй водимый многочлен. Затем находим классы вычетов ж, ж*, . каждый из которых получается с номош;ью умножения нредыдз ш,его класса на матрицу (2.

Степень

Класс вычетов

32 0 0 0 0 0 1 1 1 1

64 0 1 1 1 1 1 1 1 1

128 0 10 10 10 10

256 0 1 0 0 0 1 0 0 0

512 010000000

Теперь надо определить, выполняется ли сравнение ж" = 1 дл некоторого собственного делителя п числа 2* - 1 = 511 = 7-7Г Число п - 511/73 = 7 не удовлетворяет этому условию, поскольку мы уже видели, что а? ф х. Проверим класс ж*. В двоичной занис 73 = 1001001, так что мы подсчитаем ж* как произведение ж, и ж**. Это дает

ж-ж8.жв* = (1 Н- ж) ж«* =

= (1 Н- ж) (ж -Ь ж Н- ж» -Ь ж* -Ь ж» -f ж« + ж -f ж») = = ж Н- ж« = 1.

Следовательно, период п многочлена ж* -f ж -(- 1 равен 73. Для cpej них значений тп наиболее трудоемкой частью вычисления период неприводимого многочлена степени тп является разложение числ

- 1. Хотя в случае надобности можно получить такое разложение непосредственно, лучше пользоваться литературой, содержанкой сводные результаты но этому вопросу, основанные на многих тонких исследованиях в сочетании со значительными вычислениями. Сопоставляя результаты отчета Брилхарта и Селфриджа [1967] с цитированными ими работами, можно получить таблицу полного разложения чисел 2™ - 1 для всех т 136 и для многих больших значений т

Период многочлена / (ж) и периоды его неприводимых делителей связаны с периодом многочлена / (ж). Для того чтобы выяснить эту связь в обш;ем случае, достаточно рассмотреть лишь некоторые случаи. Во-первых, можно предположить, что многочлен / (ж) неприводим, так как если f {х) = g (ж)-h (ж), то / (ж) = g (ж) -к (ж) и можно отдельно рассматривать g (ж) и h (ж). Далее можно предположить, что t простое, так как если t = r-s, то / (ж) = / ((ж)) и анализ можно проводить в два этапа. Можно также исключить и тривиальный случай, когда t равно характеристике поля. Остальные случаи описываются следуюш;ей теоремой:

6.23. Теорема. Пусть f (ж) - неприводимый многочлен степени т над полем GF {q) с периодом, п, и пусть t - простое число, не деляиее q. Если t \ п, то период каждого неприводимого делителя многочлена / (ж) равен tn. Если t ] п, то период одного неприводимого делителя многочлена f (ж) равен п, а периоды остальных делителей равны tn.

Доказательство. Согласно свойствам круговых многочленов, доказанным в разд. 4.3, / (ж) (ж). Если t \ п, то Qm (х) = (2"" (ж), и это доказывает первое утверждение. Если t\n, то (?(") (ж) = (ж) Q (") (ж) = (?(") (ж) р /С) (ж), где

(Й, Т1) = 1

/< > (ж) - минимальный многочлен для к-х степеней корней многочлена / (ж). Каждый многочлен (ж) неприводим, и (ж) делит / (ж) тогда и только тогда, когда kt = 1 mod п. ш

*6.3. Трехчлены над..6?1М2)

Методы, описанные в разд. 6.1 и 6.2, можно легко запрограммировать. Используя современцую вычислительную машину, легко

) При средних значениях т, используя предложенные Лукасом [1878] методы, легко определить, является ли простым число 2"» - 1; когда т простое, эти числа называются числами Мерсенна, а в случае, когда {2т - 1) - простое число,- простыми числами Мерсенна. Процедура Лукаса часто, к сожалению, позволяет только определить, что данное число Мерсенна составное, не давая При этом никакой информации о его делителях.

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

Среди наиболее интересных двоичных многочленов следует выде лить трехчлены ж" + х** + 1. Если элемент а g GF (2") представляе собой корень неприводимого двоичного трехчлена степени п, то пер вые п степеней элемента а представляют собой особенно привлекатель-;! ный базис для записи поля GF (2"), так как умножение на а может! быть выполнено с помощью и-ячеечного регистра, в обратную связь! которого входит всего один сумматор с двумя входами (см. разд. 2.41). В вопросах кодирования наибольшую практическую ценность имеют поля, порядок которых не превосходит 2. Поля GF (2") при п> \i представляют больше академический, чем практический интерес, Однако имеются некоторые другие области применения регистре! с обратными связями (такие, как построение двоичных псевдослу-1 чайных последовательностей), где представляет практический инте-! рес отыскание примитивных двоичных трехчленов максимально.,! высокой степени.

Так как матрица ®, соответствующая трехчлену, содержит очень! мало единиц, то базис нуль-пространства матрицы (2 - J удобно! определять с помощью методов, описанных в разд. 2.6. Это значи-f тельно облегчает разложение двоичных трехчленов по сравнени* с произвольными двоичными многочленами.

В некоторых приложениях получение точного разложения не существенно, а требуется лишь определить, приводим многочлев или нет. Методы разд. 6.1 или другие алгоритмы [Глизон, Мак-Рэ (не опубликовано)] позволяют достаточно полно решить этот вопрос. Используя алгоритм Мак-Рэя и вычислительную машину СДС 6600 Цирлер нашел все неприводимые двоичные трехчлены степене! 1000. Используя более поздние результаты о разложении чисел 2" - 1, Брилхарт определил показатели многих неприводимыз трехчленов Цирлера. Эти результаты опубликованы Брилхарто» и Цирлером в 1969 г.

Хотя для любителей счета эти данные и представляют значи-j тельный интерес, полная картина здесь пока не ясна. Большинство! известных результатов, подытоженных Голомбом [1967], относятся только к отдельным значениям пак. Не известно даже, существуют ли примитивные двоичные трехчлены сколь угодно высокой степени. Единственная общая нетривиальная теорема о двоичных трехчленах,! доказанная Суоном [1962], определяет лишь четность числа непри- водимых множителей трехчлена + ж -f 1. Мы приведем эту тео- рему в следствии 6.696. Представляется весьма сложной даже задача] определения числа неприводимых двоичных трехчленов заданной степени, хотя, как видно из равенства 3.37 и задач 3.3 и 3.4, число! неприводимых многочленов в других больших множествах опреде-з ляется достаточно просто.

6.4. Полное разложение многочлена х"-1

В качестве одного важного примера использования алгоритма разд. 6.1 рассмотрим разложение многочлена х" - 1 над GF (д) для взаимно простых пи q.B матрице й в этом случае fij+i, j+i = 1 тогда и только тогда, когда qi = / mod п, и Qt+i, j+i = О тогда и только тогда, когда qi ф j mod п. Например, при = 15, q = 2

100000000000000 001000000000000 000010000000000 000000100000000 000000001000000 000000000010000 000000000000100 =000000000000001 010000000000000 000100000000000 000001000000000 000000010000000 000000000100000

ооооооеошоюоо

000000000000010

000000000000000 о

011000000000000 1

001010000000000 2

000100100000000 3

000010001000000 4

000001000010000 5

000000100000100 6

: - J = 000000010000001 7

010000001000000 8

000100000100000 9

000001000010000 10

000000010001000 и

000000000100100 12

000000000001010 13

000000000000011 14

с помощью соответствующих перестановок строк и столбцов матрица й - J может быть приведена к виду

6.51. Теорема. Если п = [J и, где Ui - различные простые

числа, то порядок д по модулю п равен наименьшему общему крат-

ному порядков д по модулям ni.

И ]) и м е р. Предположим, что ге = 45, g = 2. Так как порядок 2 по моду-,11<) Г) равен 4, а порядок 2 по модулю 9 равен 6, то порядок 2 по модулю 45 ранен 12.

Доказательство теоремы 6.51. Имеем q = s= 1 mod п тогда и только тогда, когда = 1 mod n\i для всех i; q" = 1 mod пА тогда и только тогда, когда т кратно порядку д но юдулю Следовательно, = 1 mod п тогда и только тогда, ь(лда т кратно каждому из порядков q но модулям пк Порядок д но лнJДyлю п равен наименьшему из таких кратных.

6.52. Теорема. Пусть п - простое число, а mj - порядок q но модулю п. Пусть д™-~ 1 делится на /г и не делится на {Это определяет число i.) Тогда для каждого j либо mji = mj, либо mji = nmj и

т, если 2<;у<г, если 7>г.

п т.

11 р и м е р. Предположим, что необходимо найти порядок 7 по модулю 1021 = 21". Выбервм 5 = 7 и п = 2. Ясно, что roi = 1 и гог = 2, так как ./™- - 1 = 48, что делится на 2* и не делится на 2. Следовательно, i = 4 11. согласно теореме, гою = 2"-* = 128.

Замечание. Если п = 1093 или п = 3511, то порядок 2 по модулю п- ])авен порядку 2 по модулю п; для остальных простых чисел <2 порядок 2 iio модулю равен п, умноженному на порядок 2 по модулю п.

Доказательство теоремы 6.52. Имеем g™j =

п-1 п-1

= 1 mod п\ так что {gjf = 1 mod п и 2 (9")" = 2 1 =

= п mod п\ Следовательно, 2 (Ч™) = О niod п и q™J - 1 = = О mod п. Перемножая эти сравнения, получаем, что q™J - 1 =

(qj - 1) [ 2 (?"•)] =0 Hiod Следовательно, m+i делит

Так как wi+i должно быть кратно т, а п простое, то имеются олько две возможности: либо mj+i = mj, либо mj = nmj.

Если q™ - 1 делится на п\ но не делится на /г*+, то mj = т для . = 2, 3, . . ., i и mi+i = пт. Для / i число д™з - 1 не делится на и, следовательно, /n+i = пт. Это получается с помощью

Ясно, ЧТО базис нуль-нространства матрицы дают многочлещ

g(i) {х) = х + х + + х; g() (х) =х + + х + ж11; g() (х) = + а:« + х + X»; g(*) (х) = х5 + х".

В общем случае если / (х) = х" - 1 над GF (д), то можно нолог

-ЖИТЬ

g{x)= х\

где К - некоторое множество чисел, замкнутое относительно умно женин на д но модулю п. Каждый из таких многочленов g (х) имее некоторый нетривиальный общий делитель с х" - 1. Таким обра! зом, для разложения многочлена х" - 1 нет необходимости выпол- пять операции над матрицей, а можно обозревать все многочлеш g (х). Каждый из многочленов g (х) имеет некоторый общий делител! с х" - 1, и он может быть найден с помощью алгоритма Евклида Применяя алгоритм Евклида к различным многочленам g (х), мв в конце концов получим разложение х" - 1 на неприводимые мнвжи тели. В большинстве случаев целесообразно начинать с разложе ния х" - 1 на круговые многочлены и использовать многочлев g (х) и алгоритм Евклида для дальнейшего разложения круговв многочленов на неприводимые множители.

*6.5. Определение степеней неприводимых делителей круговых многочленов

Так как каждый элемент порядка п в расширении ноля GF {< имеет одно и то же число сопряженных относительно GF (д) элеме: тов, то все неприводимые делители над GF (д) кругового многочле <2*" (ж) имеют одну и ту же степень. Эта степень т равна мульт: нликативному порядку числа д но модулю п. Таким образом, хот полное разложение «2" (х) может быть получено только с помощь алгоритма Евклида для многочленов, степени его ненриводимы делителей могут быть определены с помощью операций над числами

Наиболее прямым способом определения порядка числа д по моду лю п является перебор вычетов q, q, д, . . . по модулю п до тех нор. пока не будет найдено такое наименьшее т, что д™ =1 mod«, Однако при больших значениях т эта процедура становится уто: тельной. К счастью, вычисления могут быть зачительно сокращен: с помощью простых теоретико-числовых результатов, к изложени которых мы сейчас переходим.