индукции НО / ИЗ ТОГО факта, что число {q"} - i)/{q™} - 1) срав- нимо с и по модулю и, следовательно, не делится на п. щ

Последние две теоремы существенно уменьшают объем вычисле- пий для определения порядка q по модулю п, сводя эти вычисления! к определению порядков q по модулям каждого из простых делителей числа п. Таким образом, на самом деле нам надо рассмотреть только порядки числа q mod п для простых п. Наиболее очевидный резуль-1 тат в этом направлении дает теорема 6.53.

6.53. Теорема. При простом п порядок q по модулю п являет- ся делителем числа п - I.

Доказательство. Согласно теореме Ферма (4.25), д": = q mod п при любом q и любом простом п. Если q ж п взаимно просты (а мы все время это предполагаем), то gr"" = 1 mod п, Tai что п - \ кратно порядку q по модулю п. щ

Часто встречается задача вычисления q mod п для различные делителей d числа п - \. Наибольшее число вычислений приходите J выполнять для наибольшего нетривиального делителя {п - 1)/2 Дляд = 2 (или степеней 2) эти вычисления можно упростить с помо щью теоремы 6.54.

6.54. Теорема. Если п - простое число, и = +1 mod то 2("-1)2 = 1 mod п, если же п - такое простое число, что п = ±3 mod 8, то 2(n-i)li 1 mod п.

Доказательство. Пусть [х] обозначает наибольше целое число, не превосходящее х. Тогда

(п-1)/2 (п-1)/2 [(п-1)/4] (п-1)/2

2"->/ П к= П 2А;=( П 2к){ П 2Л )• й=1 h=i ft=i h=[(„ i) .]+i

Для каждого к, такого, что [{п - 1)/4] <к{п - 1)/2, выполняете сравнение - 2к = п - 2к mod п, так что

(п-1)/2 [(п-1)/4]

2("-1)/2 ] П 2/fc)(-l)<"->2-[(n-l)/4]x

(n-l)/2

x( П ( 2/t))(-l)"->-f<"-] "П

fe=[(n-l)/4]+l ft=l

Последнее равенство имеет место в силу того, что в произведев

(п-1)/2

ГТ к имеется 2к четных сомножителей ж п - 2к нечетных сомнож!

телей. Так как все А; = 1, 2, . . ., (ге - 1)/2 взаимно просты с (и простое), то можно эти множители сократить. Получаем, что

2(n-l)/2( iyn-l)/2-[(n-l)/4]

Если = ±1 mod 8, то показатель степени для -1 является нечетным; если п = +3 mod 8, то показатель - четное число, щ

В качестве примера использования этой теоремы определим степени неприводимых двоичных делителей многочлена (><25 02б) Прежде всего выпишем разложение 25 025 = 5-1 001 = 5-7-11-13. Степень этого многочлена, следовательно, равна ф (25 025) = 4-5-6-10-12 = = 14 400. Число 7 простое и 7 = - 1 mod 8; поэтому порядок числа 2 по модулю 7 делит (п - 1)/2 = 3. Ясно, что порядок 2 по модулю 7 равен 3. Каждый из остальных простых делителей 5, И, 13 блоковой длины сравним с ±3mod 8. Из теоремы 6.54 следует, что порядок каждого из этих чисел - делитель числа п - \, но не де.штель числа {п - 1)/2. Порядок 2 по модулю 5 равен 4; порядок 2 по модулю И равен 10, порядок 2 по модулю 13 является делителем 12 и не является делителем 6. Допустимы только числа 4 и 12, и так как 2* = 3 mod 13, то порядок 2 по Модулю 13 равен 12. Необходимо также определить порядок 2 по модулю 5, который равен либо 4, либо 4-5. Ясно, что правильным является второе число. Таким образом, порядок 2 по модулю 5 равен 20; порядок 2 по модулю 7 равен 3; порядок 2 по модулю И равен 10 и порядок 2 по модулю 13 равен 12. Порядок 2 по модулю 25 025 равен наименьшему общему кратному чисел 20, 3, 10 и 12, т. е. числу 60. Следовательно, многочлен «2* " - произведение 240 неприводимых множителей, степень каждого из которых равна 60.

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

Сформулируем некоторые из них в теоремах 6.55 и 6.56.

6.55. Теорема. Если п - простое и п = i (mod 3), то 2("-1)/з = 1 mod п тогда и только тогда, когда существуют такие целые X и у, что п = х -\- 27i/.

6.56. Теорема. Если п простое и п = I mod 4, то 2 " = 1 mod п тогда и только тогда, когда существуют такие целые X и у, что п = х -j- 64г/.

Доказательства} этих теорем даны Холлом [1967] и Сторером

*6.6. Четно или нечетно число неприводимых делителей /(ас) над GF{q)?

Хотя существенное улучшение общего алгоритма разложения разд. 6.1 представляется маловероятным, другие методы позволяют получить некоторую информацию о делителях многочлена с помощью значительно меньших усилий. Рассмотрим, например, школьную

формулу X = (-Ь-± УЪ - 4ас)/2а для корней квадратного уравнения аж + + с = О с действительными коэффициентами. Если q - степень нечетного простого числа, не делящего а, то эта формула остается справедливой и над GF {q). Таким образом, разрешимость квадратного уравнения над GF (q) в этом поле зависит от того, является или не является дискриминант D = ¥ - Аас квадратом в GF (q). Итак, квадратный многочлен имеет четное число (два) неприводимых делителей над GF (q), если его дискриминант есть квадрат в GF (д), и имеет нечетное число (один) неприводимых делителей над GF {q) в противном случае. Это простейший пример одного общего результата, известного как теорема Штикельбергера. Для доказательства этой теоремы определим сначала дискриминант произвольного многочлена.

6.61. Определение. Дискриминант D многочлена / {х) =

= а W (ж - ocj) определяется равенством

Dif)==an-2 ЦЦ (ai-aj)K

Как мы увидим, дискриминант является частным видом одной функции от двух многочленов, называемой результантом и определяемой следующим образом:

6.62. Определение). Результат двух многочленов

f{x) = a П (x-ai), g{x)-=b П (x-pj)

i=l j=l

задается равенством

R(f,g)=ab П П (а,-Р,).

4=1 3=1

Из этого определения сразу вытекают следующие свойства результанта. (Доказательство (6.622) следует неносредственно из (6.627).)

%.т. R{g, f) = {-\Г RU, g).

6.622. Если g{x) =f {х) qix) + r (ж), то R (/, g) =

6.623. Если f (x) и g (x) имеют общий делитель положительной степени, то R (f, g) =0.

1) Это определение восходит к Ван-дер-Вардену [1931]. Предупредим читателя, что некоторые другие авторы, включая Суона, определяют результант равенством R (/, g) = R (g, f). Заметим также, что в определении Ван-дер-

Swan VdW

Вардена участвует множитель (-Ц5 28].

6.624. Если а и Ъ ~ константы, не равные одновременно О, то R (а, Ь) = 1.

6.625. Если /(а;) = /<1>(а;)/<2)(х), то

R{f,g) = R{P,g)R{f\g).

6.626. Если g (х) = gl (х) g<2> (х), пю

Л (/,g) = i?(/,g<i) (/,§<)•

6.627. R(f, g) = a™ П («0 = (-!)""&" П / (Р.).

i=l j=l

Свойства 6.621-6.624 позволяют вычислить R (/, g), применяя к f (х) ж g (х) алгоритм Евклида. Это означает, что результант / (х) н g (х) может быть выражен через произведения, частные, суммы и разности коэффициентов этих многочленов. В частности, если t (х) я g (х) - многочлены над полем F, то R {/, g) F, даже если корни f (х) ж g {х) лежат не в F.

. Теорема 6.63 дает выражение для дискриминанта нормированного многочлена / {х) степени п.

6.63. Теорема.

£>(/) = (- if--"R if, /) = (- !)"("-

Доказательство. Согласно свойству 6.627,

/)= П /(«ft). ft=i

lor да

f(x)-= и (x-cci), f{x} и {х-at).

1=1 j гф]

/(a*) = S П («/.-«;)= П («й-аО.

i гфЗ i

(/. /) = [lII(«ft-aO =

г h гфк

-III. П («.-«,)][[] П(«*-аО] = (-1)""~£>(/).,

lS:i<ft5;n

lS:A<t5in

Используя это соотношение между дискриминантом и резуль-jtom, можно вывести формулу для дискриминанта произведения.

6.64. Теорема. Если g (х) и h (х) - неприводимые многочлены, то

D (gh) =D(g)D (h) [r (h, g)]\

Доказательство. Пусть степени g (x) и h (x) равны соответственно i и /. Тогда

(-+->d (gh) = r {gh, igh)) = = r {gh, gh + gh) = r {g, gh + gh) r {h, gh + gh) = r {g, gh) r {h, gh) = r {g, g) r {g, h) r {h, g) r {h, h) =

= ( l)Ui-l)/2£, Д ) ( yij ( l)i(i-l)/2£,

Утверждение теоремы вытекает из равенства

2 2 r7i- 2

Повторное использование теоремы позволяет вычислить дискриминант произведения к нормированных многочленов /i> {х), / {х),... /"(а;). Имеем

D (п Г)=D ш /О (/) [R Ш / =

i=l i=l i=l

i=l i=l

6.65. Теорема.

>(Пг) = [.ПЬ(/<*)][ П. II я/<)Г.

li<J=£ft

Мы можем теперь вычислить непосредственно дискриминанты некоторых многочленов. Рассмотрим, например, квадратный трехчлен ах -\- Ьх -\- с. Имеем

D{ax + bx + c) = aW (« + -7 + "") = =-.-aR(2x + ±,x+x + )

Квадратный трехчлен является частным случаем трехчлена общего вида ж" -\- ааг -\- Ъ, дискриминант которого был вычислен Суоном [1962].

6.6. Четно или нечетно число неприводимых делителей?

6.66. Лемма Суона. Результант двух биномов определяется равенством

R {х Г, v) = ( 1) (V™ - Г),

где d = н. о. д. (/, к) и т = jk/d.

Доказательство. Если, а - примитивный корень /-й степени из единицы, то

R{x-l\x-v)== nKiaf-v"]-

i = l

={-i)TY[[(j)

Так как порядок a** равен j/d, то

{x-l\x-v) = {-i)T[(y-iJ = {-iy{v--in.M

6.67. Теорема Суона. Пусть n> k> 0. Пусть d= п. о. р,. (п, к); n=--Nd; k = Kd. Тогда дискриминант трехчлена х"-\-азb определяется формулой

D{x + aa + b) = = (- 1)"("-1)/(-1){n-k)-Vay.

Доказательство. Для f {х) =--х + ах-\-b имеем D {f{x)) = (- 1)"("-)/2д („„-1 akx>-i д)). R (тгх"-1 -f акх>-\ f {х)) --= R (х-, / {х)) R{n,f {х)) R {x + «"Ы, / {х)),

Л(п,/(х)) = п" = п Л (ж"-" + n-iflA;, / (х)) = R (х"- + re-iflA;, х" (х"-" -f п-аА;) + -Н а (1 - п-А;) х + 6) = Л (х""" + п-ак, а (1 - пА;) х -f Ь) = = (а (1 - w-iA;))"-" Л (х"- -х - v").