и так как Тг(а;) = Тг (ж), то

;(/)

L [л т J

= Trip (/)].,

В общем случае, если / {х) - некоторый многочлен над GF (2") и ге > 1, то для определения четности числа неприводимых делителей / (ж) надо отдельно вычислить т) (/) и (/) и затем найти след /т). Однако если / {х) - многочлен над GF (2), то возможно сокращение процедуры счета. Можно рассматривать / (х) как многочлен с целыми рациональными коэффициентами и вычислять его дискриминант по модулю 8 1). Если Z) = 1 mod 8, то г = тп mod 2 (так как т] = 1, g = О и Тг (/т1) = 0]; если Z) =з 5 mod 2, то г тга mod 2 [так как •П = 1, I == 1 и Тг (/т)2) = 1]. Если D щк 1,5 mod 8, то D четно и / (х)имеет кратные делители над GF (2).

Сочетание двоичного варианта теоремы Штикельбергера и теоремы Суона приводит к следующему утверждению.

6.698. Следствие Суона. Пусть п > к 0. Предположим, что точно одно из чисел п, к нечетно. Многочлен х" + х* + 1 имеет четное число неприводимых дзлитглей над GF (2) тогда и только тогда, когда

1) ге четно, к нечетно, п Ф 1к; пк/2 = О или 1 mod 4;

2) ге нечетно, к четно, к \ 2п, п= ±3 mod 8;

3) ге нечетно, к четно, к \ 2ге, ге = ±1 mod 8. Доказательство. Из теоремы Суона 6.67 вытекает, что

!) = {- Ife-i)/ ( 1) („ kf-kt-По предположению D, d, п - к и iV - Z - нечетные числа, так что

Z> = ( - 1)«("-1>/2 ( N ) (jjjp 8).

Поэтому утверждение теоремы следует из рассмотрения вычетов числа D mod 8 в каждом из следующих четырех случаев:

1) ге четно, к нечетно, N > 2;

2) ге нечетно, к четно, Z > 2;

3) ге нечетно, к четно, К = 2;

4) ге четно, к нечетно, N = 2.

В случае 4 Z) = 5 (mod 8), и этот случай можно дальше не рассматривать. I

1) Двоичный вариант теоремы Штикельбергера был доказан Карлидом [1953], Даленом [1955] и Суоном 11962], однако обобщение теоремы на случай поля GF (2") в теоремах 6.69 и 6.95 представляется новым. Частный случай для deg / = 2,или 3 и произвольного п был доказан ранее Берлекэмпом, Рамсеем и Соломоном [1967].

(alp) =

*6.7. Квадратичный закон взаимности

Для произвольного числа а и простого числа р можно определить символ Лежандра {alp) следующим образом:

6.71. Определение.

1, если уравнение х = а имеет ненулевое решение в GF (р);

-1, если уравнение х = а не имеет решений в GF (р); О, если р делит а.

Символ Лежандра возникает в приложениях теоремы Штикельбергера для определения мультипликативного порядка числа а по модулю р, при определении степеней неприводимых множителей многочлена (х) над GF (р), при изучении кодов, задаваемых квадратичными вычетами (разд. 15.2) и во многих других вопросах теории чисел. Если уравнение = а имеет ненулевое решение в GF {р),то а называется квадратичным вычетом по модулю р, а если ненулевых решений нет, а-квадратичный невычет.

Если а - квадратичый невычет, то многочлен х* - а неприводим над GF (р), и Ya 6 GF (р); если а - квадратичный вычет, то х - а разлагается над GF (р) и ]/а б GF,{p). В любом случае la 6 GF (р). Элемент Уа лежит в подполе GF {р) тогда и только тогда, когда Ya=Ya. Так как (a<*-i)/2)2 = 1 и все корни уравнения X* - 1=0 исчерпываются числами х = ±1, то а-)* = = ± 1 mod р. Следовательно,

(a/p) = a(P-i)2niodp.

Это сравнение носит название критерия Эйлера. Легко доказываются леммы 6.721-6.723.

6.721. Лемма. {аЫр) = {а/р) {Ыр).

6.722. Лемма, {-i/p) = (-l)(»-iV

6.723. Лемма. (aVp) = 1.

6.724. Лемма.

{2/р) =

если р = ± 1 mod 8; если p = ±3mod8.

Доказательство леммы 6.724 следует непосредственно из теоремы 6.54.

Рассмотрим теперь разложение многочлена / (х) = х" - 1 над GF (р), предполагая, что пир - различные нечетные простые числа. Мы уже знаем, что х" - 1 = (х - 1) (х). При этом каждый неприводимый делитель многочлена (х) над GF {р) имеет

степень т, где т - мультипликативный порядок числа р по модулю п. Таким образом, число различных неприводимых" делителей многочлена (ж" - 1) над GF (р) равно г = I + (п - 1)/т. По определению символа Лежандра число т делит (п - 1)/2 тогда и только тогда, когда (р/п) = 1. Следовательно, (-l)(n-i)/m д (-1) = = - (р/п), где г - число неприводиийлх делителей многочлена (ж" - 1) над GF (р).

Дискриминант многочлена / (ж) = ж" - 1 выражается формулой d(f)= ( 1)"("-1)/2 R(nx\ ж" - 1) = ( 1)"(п-2)/2. ТеОрО-

ма Штикельбергера 6.68 утверждает, что если многочлен / (ж) степени л является произведением г неприводимых множителей над GF (р), то га = г mod 2 тогда и только тогда, когда (D/p) = 1, где через d обозначен дискриминант / (ж). Иными словами, (D/p) =

Если / (ж) = ж" - 1, где п - простое нечетное число, то

(„« ( 1)п(„-1)/2/,) ( 1)П ( 1)Г ( ( (/j (/

Это соотношение позволяет выразить квадратичный вычет (р/п) через? квадратичный вычет Ыр). Учитывая, что (-l)"("-i)/a - ( 1)(«-1)/2, получим:

{pin) = (га» (-1)(«-1)/2/р) = (га/р) (ra"-V;)) ((-l)("-i)/Vp).

Так как ra"-i = (ra("-i)/2)S то (ra"-Vp) = 1. Так как (-1/р) = = то ((-1)("-1)/2/р) = ( 1)(п-1)(Р-1)/4. Следовательно,

(р/й) = (га/р) (-1)(«-1)(Р-1)/4 . Это эквивалентно следующей теореме 6.73;

6.73. Теорема Гаусса о квадратичном законе в 3 а им н о с т и. Если пир- различные нечетные простые числа, то

(р/га)(га/р) = ( 1)<"-ИР-1)/4

Приведенное выше доказательство принадлежит Суону [1962].

Закон взаимности квадратичных вычетов очень полезен при фактическом вычислении символов Лежандра.

6.74. Пример. Чему равны степени неприводимых делителей над GF (19)?

Решен ие. Задача состоит в вычислении мультин ликативного порядка числа19 по модулю 257, что сводится к вычислению 19* или (19/257). Используя закон взаимности, получаем, что

(19/257) = (257/19) = (10/19) = (2/19) (5/19) = = (2/19) (19/5) = (2/19) (4/5) = (2/19).

Так как 19 = 3 mod 8, то (2/19) = -1 и 19*« = -1 mod 257. Так как порядок числа 19 по mod 257 делит 256 и не делит 128, то он равен 256. Следовательно, многочлен (J* неприводим над GF (19).

Другие факты о квадратичном законе взаимности можно найти в книгах по теории чисел, в частности в книгах Маккоя [1965] и Нэд-жела [1951].

Задачи]

6.1. Разложить на неприводимые множители следующие многочлены над GF (2):

(a) -Ь хч -t- + -f X* + ж + 1;

(b) х" + хз + 1;

(c) х23 + 1; •

(d) х« -f 1.

6.2. Определить периоды многочленов из задачи 6.1.

6.3. Простое число р называется примитивным делителем числа 2"» - 1 тогда и только тогда, когда порядок 2 по модулю р равен т; простое число р называется алгебраическим делителем числа 2™ - 1 тогда и только тогда, когда порядок 2 по модулю р является собственным делителем т.

(a) Доказать, что если р - примитивный делитель числа 2™ - 1, то р = = 1 mod т. Если т нечетно, то р = ± 1 mod 8; если m = ± 2 mod 8, то р = =: 1 или 3 mod 8; если m = О mod 8, то р = 1 mod 2т.

(b) Разложить 211-1 и (2 - 1)/(2б - 1) = 1 082 401.

(c) Доказать, что если m = ± 2 mod 8, то произведение всех примитивных простых делителей числа 2»» - 1 сравнимо с 3 по модулю 8. Указание. Использовать индукцию для <?<а)-

(d) Используя таблицы Каннингема, опровергнуть следующее утверждение: если m = ± 2 mod 8 и если р - примитивный простой делитель числа 2т - 1, то р = 3 mod 8.

6.4. Доказать или опровергнуть:

(a) Если р - простое число, такое, что р =. Z mod 8, то мультипликативный порядок числа 2 по модулю р равен р - 1.

(b) Если р - простое число, такое, что р s - 3 mod 8, то мультипликативный порядок числа 2 по модулю р равен р - 1.

6.5. Число Ъ называется примитивным по модулю п тогда и только тогда, когда мультипликативный порядок Ь по модулю п равен ф {п). Доказать или опровергнуть:

(a) Если число 2 примитивно по mod га, то (х) неприводим над GF (2).

(b) Если (?(п)(х) неприводим над GF (2), то га - степень простого числа р, причем р = ± 3 mod 8, р I л, или р =га--1, а число 2-примитивно по модулю га.

(c) (?("> (х) - неприводим над GF (д) тогда и только тогда, когда одновременно выполняются следующие условия:

(1) п = р или 2р«, где р - нечетное простое число;

(2) (р, д) = 1;

(3) порядок q по модулю р равен р - 1;

(4) или е == 1 или порядок д по модулю р равен р (порядку д по модулю р).

6.6. Доказать или опровергнуть:

(а) Для каждого натурального т существует по меньшей мере один круговой многочлен степени т, неприводимый над GF (2).

(Ь) Для каких значений m < 30 существуют неприводимые круговые двожчг ные многочлены степени m и каковы их порядки? Начало:

6.7. Для каких значений ] а к неприводимы над GF (2) следующие многочлены?

(а) х2-зЧхзЧ1;

(b) x4-5-3 + 5.3J+i.

(c) х-б-з + 3.5".3 + г-Б--з + Б.З + 1.

(d) x5-3lVx2-3l+l;

(e) б-з.т + 4.3.7i + 2.3.7i + з.т- + 1. Найти периоды этих многочленов и их разложения.

6.8. Доказать или опровергнуть:

(a) Ни один двоичный трехчлен не может иметь неприводимых делителей периода 5.

(b) Если некоторый двоичный трехчлен имеет неприводимый делитель периода га, то существуют двоичные трехчлены степени <Сп, обладающие неприводимыми делителями периода п.

(c) Если га >- 5 - простое число и 2 - примитивно по модулю га, то ни один двоичный трехчлен не имеет неприводимых делителей периода га.

(d) В условиях задачи (с) период не может быть равен га ни для какого к.

(e) Если некоторый двоичный трехчлен имеет неприводимый делитель периода ге и если (га, к) = i, то существует двоичный трехчлен, обладающий неприводимым делителем периода кп.

(f) Для га = 1, 3, 5, 7, 9, . . ., 41 определить, существует ли двоичный трехчлен, обладающий неприводимым делителем периода п.

Указание. Для га == 17, 23 и 41 воспользоваться соответственно результатами разд. 5.7, 5.6 и 5.7.

6.9. Используя следствие Суона, доказать, что двоичный трехчлен степени ге неприводим, если

(a) га = О mod 8.

(b) re = 13 или 19 mod 24 и каждый делитель числа п сравним с 1 по модулю 6.

(c) га - простое число, га > 3, га = ± 3 mod 8, га = 3 или -1 mod 7.

Глава 7

Двоичные БЧХ-коды, исправляющие многократные ошибки

Для построения двоичного БЧХ-кода, исправляющего t ошибок, прежде всего надо найти неприводимый двоичный делитель / (х) кругового многочлена Степень / (х) равна мультипликативному порядку т числа 2 по модулю п. Пусть а GF (2""). Тогда двоичный БЧХ-код с блоковой длиной п, исправляющий t ошибок, строится как циклический код, порождающий многочлен которого равен произведению различных минимальных многочленов для элементов а, а, а, а*, . . ., а~, а. БЧХ-коды для и = 2™ - 1 называются примитивными, а коды для остальных нечетных п непримитивными.

7.1. Примеры

Используя таблицу 4.4, можно построить все двоичные БЧХ-коды с блоковой длиной 31. Эти коды имеют следующие порождающие: многочлены:

- t = I, д(х) = ikf(i) (х) = 1 -f X* -f x или, в сокращенной форме, g = 101001;

t =2, g{x) = M\x)M\x) = l-x + x+x<+x+x+>,

g = 10010110111;

t = 3, gix) = M<i>(x)M(3(a;)M<6)(:c), = 1111010111110001;

f=4 или 5, g(x) = M<i> (x)M<3>a;M5>xM> (x), g= 101010110110010001101;

t = 6 или 7, g(x) = M4(x)M3)()A/«(:c)M<7>xikf<"(x), g= 11100100010101111011010011; f = 8, 9, 15, g (x) = M<i (x) M<3 (x) Af <5 {x) Af <" (x) j¥<" (x) Afi) [x), g = 1111111111111111111111111111111.