кратность каждого корня А (z) равна р, то А (z) - скалярное кра ное многочлена [L (z) - и]т = [L (z)]p- мр, т. е. А (z) - аффи ный многочлен, щ

Различные корни произвольного аффинного многочлена образуя аффинное пространство. Пересечение любых двух аффинных пр странств снова является аффинным пространством. Так как обг корни любых двух многочленов являются корнями их наибольше! общего делителя, то п. о. д. двух аффинных многочленов с разл1 ными корнямиявляется аффинным многочленом с различными koj ними. Более того, п. о. д. многочленов Ат и Вт> равен н. о. д. мнА гочленов А ж В, возведенному в наименьшую из степеней р* или Отсюда, в частности, вытекает теорема 11.331.

11.331. Т е о р е м а. Я. о. 9. двух аффинных многочленов являе ся аффинным многочленом.

Если нуль - корень двух аффинных многочленов, то нуль являе! ся также корнем их п. о. д. Поэтому справедливо следующее утвер); дение.

11.332. Т е о р е м а. Я. о. 9. двух линеаризированных многочлене является линеаризированным многочленом.

Если А VI В - два аффинных многочлена и А делит В, то корь многочлена А образуют подмножество множества корней В. Аффи ное пространство корней А является, таким образом, аффинш подпространством пространства корней В. Множество всевозможн разностей корней А (т. е. совокупность всех корней линеаризирова! ной части А) есть подмножество множества всевозможных разноса корней В - т. е. совокупности корней линеаризированной части (см. доказательство теоремы 11.32). Так как кратность любого Kopi линеаризированной части аффинного многочлена совпадает с кра5 ностью корней исходногб аффинного многочлена, то получаем еле дующий результат.

11.34. Теорема. Если А и В - аффинные многочлены и делит В, то линеаризированная часть А делит линеаризированщ часть В. Обратно если L и М - линеаризированные многочлены ami и L делит М, то L (z) - L (г) = L (z - г) делит М {z - г) * = М (z) - М (г) для любого г, лежащего в поле коэффициент А и В.

Часто необходимо знать, лежат ли в поле GF (/?"*) все корни зада ного аффинного многочлена А {z) = L (z) - и. Если А (z) дела zP"* z, то все корни А (z) лежат в GF (р"), но если А (z) не дел1 zP"- z, то часть корней А (z) лежит вне GF (р"). Согласно Teoj

ме 11.34, А (z) делит zp™ - z, только если L (z) делит zp"* - z. Если же L (z) делит zp*" - z, то А (z) = L (z) - и делит zp™ - z тогда и только тогда, когда существует такой элемент г, что L (г) = и п гр"* - г = О, т. е. г g (р"*). Ясно, что для некоторых и существуют такие элементы г GF (р™), что L (г) = и. Такие и образуют линейное пространство, называемое ранговым пространством линеаризированного многочлена L. Если и принадлежит ранговому пространству, то L (z) - и делит zp"* - z, и все корни многочлена L (z) - и лежат в GF (р). Если же и не принадлежит ранговому пространству, то не существует такого г £ GF {р), что L (г) = и, и все корни многочлена L (z) -и лежат вне GF {р). Вопрос о принадлежности элементов из GF {р) ранговому пространству заданного линеаризированного многочлена L (z) полностью решается следующей теоремой.

11.35. Теорема. Пусть L (z) - произвольный нормированный линеаризированный многочлен над GF (р™), делящий zp™ - z. Тогда существует единственный нормированный линеаризированный .многочлен L* (z), делящий zp"* - z и такой, что:

11.351. L*{L{z)) = zP-z.

11.352. L{L*{z)) = zP--z.

11.353. Корни L (z) =и лежат в GF (р™) тогда и только тогда, когда L* (и) = 0.

11.354. Корни L* (z) = и лежат в GF (р"") тогда и только тогда, когда L (и) = 0.

Многочлены L (z) и L*l (z) будем называть дуальными.

11.355. П р и м е р. Пусть L (z) = z-f z над GF (2). Тогда

L* (z) = z" + z» -f z* + z2 + z и можно проверить, что

L» (L (z)) = (z2 + z)" + (z2 + z)« + (z2 + z)* + (z2 + z)2 +

+ (z2 + z) = z32 + z = z32 - z,

L (L* (z)) = (zi" + z8 + z* + 2 + z)H(z"+z8 + z* -f z2 + z) =

= z»2 -f z = 2.

Корни уравнения z + z = и лежат в GF (2*) тогда и только тогда, когда -f + ы* + -- м = О, т. е. когда Тг (и) = Q. Корни уравнения z" + z -- 2* + 2 + 2 = м лежат в GF (2*) тогда и только тогда, когда и + и = 0; т. е. когда и £GF (2).

Тогда

р-1 р-1

ь*(2)= п п

р-1 тп

П [z- 2 CiL{ri)].

р-1 р-1 р-1 ft

L{z)= П П ••• П (z-S «го)

р-1 р-1

ZP™-Z= П П р-1 р-1

= II п

р-1 т

i=ft+l

- р-1 т

П [b(z)- 2 Cib(ro] =

ft+i

t=fe+l

= L*(L(z)).

Это доказывает утверждение 11.351. Равенство

р-1 р-1

zp™-z= П П

П [b(z)- 2 ciL{rt)]

fe+i

i=ft+l

задает разложение многочлена zp"* - z на множители вида L (z) - где каждое и является корнем L* (z). Это доказывает утвержЯ

1) Таблицы loga и antilogy приведены в приложении А.

k i i г i

справедливо тогда и только тогда, когда gu = K~jfj Для всех к. «

11.38. Следствие. Если L (z) - линеаризированный много-ч.ген над GF (р), то L делит z*-" - z тогда и только тогда, когда

Вообще над GF {р) линеаризированные многочлены - j

И 2 2" дуальны друг другу.

ft=0

11.356. Пример. Рассмотрим более сложный случай дл поля GF (2), полагая а корнем многочлена а; + + 1 ). Пуст

L (z) = z* + az + aiz = z (z - a) (z - a«) (z - a),

L* (z) = z8 + a"z* + aiz + a"z =

= z (z - a) (z - a) (z - a") (z - a") (z - a") (z - a) (z-aH

Установив, что L* (a) = a", (a) = L (a) = a", L (a«) = и L (a*) = a", все случаи утверждений 11.353 и 11.354 лег получить как следствия этих равенств; например,

L* (а + а) = а" + а =

Доказательство теоремы 11.35. Пусть г, Гз, . . . . ., - базис пространства корней многочлена L, и пусть Га, . . ., Tfe, Tfe+i, rfe+2, . . ., r,„ - базис поля GF (р"*) над (р Положим

ние 11.353, а также единственность многочлена, дуального к многочлену L, так как корневое пространство многочлена, дуального многочлену L, должно быть ранговым пространством L.

Для доказательства утверждения 11.352 подсчитаем L (L* {L (z))) == ==L(z™ - z) = L (z™) - L (z). Так как L - линеаризированный многочлен над GF {р), то L (z™) = [L (z)]*"" и, следовательно, L {L* {L (z))) = [L (z)]P™ ~ L (z). Полагая у = L (z), получаем, что L {L* (y)) = z/" - y. Это равенство должно быть тождеством относительно у и потому L {L* (z)) = z™ - z, что доказывает утверждение 11.352.

Для доказательства утверждения 11.354 выберем базис г*, г*, ... . . ., Гт-h в корневом пространстве многочлена L* и базис г*, г*, ... . . ., Гт-h, • ., Гт в GF {р). Остальная часть доказательства является двойственной к доказательству утверждения 11.353. щ

Если все коэффициенты линеаризированного многочлена лежат в основном поле GF (р), то на некоторые вопросы о его свойствах можно ответить с помощью рассмотрения ассоциированного с ним многочлена, определяемого следующим образом.

11.36. Определение. Если /, g GF (р) для всех i, то многочлены F (z) = 2 /jZ" и / (z) = 2 /jZ* называются ассоциированными;

F - линеаризированно ассоциированный с f; f - стандартно ассоциированный с F.

Плодотворность этого определения видна из следующей теоремы:

11.37. Теорема. Если F и G - линеаризированные многочлены над GF (р), af и g - стандартно ассоциированные с ними многочлены, то F делит G тогда и только тогда, когда / делит g. Если g = hf, то G = H{F) - F{H), где Н-линеаризированно ассоциированный с к.

Доказательство. Каждое из равенств

gkZ=J.hiZfjz

стандартно ассоциированный с ним многочлен I (г) делит z"* - 1 Если L делит z**™ - z, то стандартно ассоциированный с L* {дуалъ ным к L) многочлен задается равенством

l*(z) =

11.381. Пример. В соответствии с разложением z"* - 1

= (z - 1) 2 2 можно записать разложение для линеаризирование

ft=0

m-l

ассоциированного многочлена z™ - z = (z - z) 2 2" • Эти раз

ложения дуальны друг другу.

Используя последнее следствие, можно определить, число эле ментов поля GF (q), обладающих т линейно независимыми сопря! женными относительно GF (д) элементами Если v GF {д), тй

qm-l

линейно зависимы тогда и только тогда, когда

существуют такие элементы /о, Д, . . ., fm-i£GF(g), не равнь одновременно нулю, что 2/1" = О- Так как z; - корень много

членов 2 /iz и z™ - Z, то он является также корнем их н. о.

Н. о. д. этих двух лиаеаризированных многочленов также линеарв зирован. Таким образом, все сопряженные с v элементы линеш зависимы тогда и только тогда, когда v является корнем некоторог

многочлена 2г2 делящего z™ - z.

* . j

Пусть т = рп и н. о. К- («, р) = 1, так что z" - 1 = (z" - 1)"

.-=[!(§()) р, где g-t) (z) - различные неприводимые делители мнС

гочлена z" - 1. Обозначим через степень многочлена g- (z); Ясно, что 2 ft = Максимальный собственный делитель много

члена z"" - 1 имеет вид Л") = (z" - i)/g). Каждый собственнь делитель многочлена z" - 1 делит но меньшей мере один из эт1 максимальных делителей. Каждому максимальному делителю много члена z" - 1 соответствует максимальный линеаризированный дел1

тель многочлена z™ - z, а именно Ж**) (z) = 2 Mz; deg Я*)

=,g,<™-*ft\ Элемент vGF (g) имеет m линейно независимых сонрш

1) Если q - степень простого числа, то линеаризированный многочле следует определить как многочлен вида Liz. Все предыдущие результат

остаются в силе.

женных тогда и только тогда, когда он не является корнем пи одного из этих многочленов Я<).

Н. о. д. нескольких максимальных делителей многочлена z" - 1, скажем, /i(i), Ы), Л) равен (z" - l)/g(i)g-(2)gr(3) имеет степень т - - (di+d+dg). Соответственно п. о. д. многочленов Я), Я) и Н) является линеаризированным многочленом степени gr(m-di-d2-d3). Если случайным образом выбирается элемент поля GF (д), то вероят-писть того, что он есть корень Н, равна д~, вероятность того, что он является корнем Я(2), равна д-", а вероятность того, что он одновременно является корнем Н() и H-l, равна 5-1-2. Таким образом, вхождение элемента в качестве корня в ЯЧ) и в Я) - независимые события. То же самое можно сказать о Я), Я(2), Я) ц т. д. Вероятность того, что случайно выбранный элемент поля GF (д) не есть корень Я**), равна 1 - Применяя теорему

умножения вероятностей, заключаем, что вероятность того, что случайно выбранный элемент поля GF (д) не является корнем ни одного из многочленов Я<*), равна fJ (1 " Я~)- Это дает теорему 11.39. "

11.39. Теорема. Число элементов поля GF {д""), обладающих т .тнейно независимыми сопряженными относительно поля GF (д), равно

гОе {dft} - степени различных неприводимых делителей многочлена Z" - 1 над GF (д).

11.391. Пример. Рассмотрим поле GF (2*). Над GF (2)

Zl* - 1 = (z - 1)2 = ((?(1)(?())2,

где (1) - неприводимый многочлен степени 1, а - произведение двух неприводимых кубических многочленов. Итак, - I, c/j = 3 = 3, и число элементов поля GF (2*), имеющих 14 линейно независимых сопряженных относительно GF (2) элементов, равно 2". 1/2-7/8-7/8 = 6272. Эти элементы лежат в 6272/14 = 448 классах сопряженных (над GF (2)) элементов. Существует 448 неприводи-jrux двоичных многочленов 14-й степени, корни которых линейно независимы.

Читатели, относянщеся с недоверием к вероятностной аргумента-дпи, использованной в предыдуп!,ем доказательстве, могут доказать этот же результат с помощью комбинаторных методов. С нашей точки зрения вероятностный подход делает результат более прозрачным.

Как указал Кац [1959], вероятностный подход к вопросам перечисления нашел широкое применение во многих различных задачах.