ПОЛЯ ГАЛУА­



GF(p^m), GF(p^2), GF(27)=GF(3^3), GF(5^m), ..., GF(57^m)

© Nickolay A. Balonin, 1.05.2015


GF(p2), GF(3m), GF(5m), 2≤m≤10; GF(7m), 2≤m≤8; GF(11m), 2≤m≤6; GF(13m), 2≤m≤6; GF(17m), 2≤m≤6; GF(pm), 2<p≤57, m=3,4; there is tuning to construct other finite fields based on irreducible polynomials xm=sxd+r, d=GFd, s=GFs, r=GFr.

Как построить конечные поля (поля Галуа)? Ответ на этот вопрос с примерами алгоритмов и самими алгоритмами, запускаемыми on line, ниже.

ВВЕДЕНИЕ


Пояснение. Арифметику "бесконечных" наборов чисел, изучаемую в начальной школы, в средней школе венчают комплексные числа, состоящие из m=2 образующих. Расширить состав образующих нелегко, впервые это обнаружил Гамильтон, пытаясь конструировать гиперкомлексные числа. Арифметика конечных наборов p чисел более примитивна по привлекаемому материалу, но она же дает и больше свободы – в ней не ограничено число образующих m. Это арифметика векторов размера m, где m=2 – случай, восходящий к комплексным числам. Полиномиальная интерпретация векторов как наборов коэффициентов полиномов удобна для пояснения и запоминания правил их сложения и умножения. В полиномиальной арифметике сложение и вычитание по модулю p заведомо не повышает степени полинома. Проблемно лишь умножение. Его результат, чтобы вернуть показатель старшей степени обратно, делят на некоторый неприводимый многочлен степени m и находят остаток от деления. Единственная сложность: когда коэффициенты полиномов заданы в поле GF(p), расчет остатка проводится с учетом арифметики алгебраического сложения по модулю, расчет дает полиномы с положительными коэффициентами. Конечное поле связано с мультипликативной группой Галуа – циклической группой, используемой для построения ортогональных матриц Адамара, в теории кодирования и т.п. Все это дано ниже, вплоть до исполняемых on line алгоритмов. Время таких систем пришло, они очевидно вытеснят книги без исполняемых алгоритмов.

Множество элементов, на котором определены две операции сложения и умножения (правила взяты из арифметики), называют полем. Поля с конечным числом элементов называют полями Галуа (Galois Fields) по имени их первого исследователя и обозначают GF(p), p – простое число, или, в общем виде, GF(pm).

В более узкой по материалу, чем теория поля, теории групп выделяют бинарную операцию, оставляя во внимании единичку, обратный элемент и ассоциативность (независимость порядка применения операции к элементам a(bc)=(ab)c. Таковы целые числа с операцией сложения. Группа, в которой любые два элемента коммутируют, называется коммутативной или абелевой.

Теория полей и теория групп смыкаются – важнейшим свойством конечных полей является то, что множество всех ненулевых элементов конечного поля образует группу по операции умножения, т. е. мультипликативную группу порядка p–1.

Квадратичные вычеты. Операция "умножения" не выводит числа поля Галуа GF(p) за пределы этого поля, по определению. Она связана с "возвращением" квадратов чисел в пределы выбранного числового диапазона.


Те места, куда квадраты чисел "возвращаются", называются квадратичные вычеты (quadratic residues). Прочие числа числового поля называются квадратичные невычеты.

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

Циклические группы. Мультипликативную группу поля образует поле Галуа GF(p) без нулевого элемента. Эта группа G=GF(p)*, звездочка свидетельствует об удалении 0-й, является циклической, т.е. в ней есть порождающий элемент, а все остальные получаются возведением в степень порождающего. Любая циклическая группа – абелева, т.е. ее операция коммутативна.

Замечание: в высшей алгебре разница между умножением и сложением относительна, при сложении понятие "степень" n элемента a циклической группы имеет вид na. Порождающим элементом набора целых чисел будет 1.

Числа 0, 1, 2,…, p–1, если операции сложения и умножения выполняются по модулю p, образуют простое поле. Таблицы сложения и умножения отличаются от привычных для первого класса школы лишь тем, что содержат остатки деления на p.

Пример 1. Наименьшее число элементов, образующих поле, равно 2. Такое поле должно содержать 2 единичных элемента: A=0 относительно операции сложения и B=1 относительно операции умножения. Их можно понимать, как 0 и 1, или абстрактно, как A и B. И исследовать таблицы на предмет соблюдения, для операций с ними, всех правил арифметики.

+
A
B
A
A
B
B
B
A
A
B
A
A
A
B
A
B


Пример 2. Поле с конечным числом элементов GF(3) .

+
A
B
C
A
B
C
A
B
C
A
B
C
A
B
C
A
B
C
A
A
A
A
B
A
B
C
C
A
C
B


Поле GF(p), p – простое число, имеет p элементов, нумеруемых как 0, 1, 2,..., p–1. Арифметика в GF(p), это арифметика по модулю p. Поэтому, обозначив элементы целыми числами, несложно сгенерировать таблицы сложения и умножения, и к ним, весь корпус арифметических функций.

Примитивные элементы полей Галуа


Элементы показательной функции xk в теории групп называют косетами (со наборами), по нашему это элементы прогрессии. Векторные элементы xat+k, функции от t, называют циклотомическими косетами (орбитами, в сходной интерпретации). Линейные комбинации орбит используются при поиске бициклических матриц максимума детерминанта. Ускорить поиск экстремальных прогрессий помогают исследования их симметрий и ограничения на суммы элементов, см. cyclotomic cosets.

Возведение в степень обнаруживает различие между элементами поля Галуа. Как можно заметить, если возводить в степень числа 3 либо 5 в поле Галуа GF(7), мы получим все элементы поля, кроме 0. Такие числа называются примитивными элементами.

Исключив нулевой элемент и взяв за основу примитивный элемент, получим циклическую группу GF(p)*. Элементы циклической группы – степени A, A2, ..., Ap–1=1, поэтому ее обозначают также <A> или F\{0}, F – конечное поле. Как видно по G(7), помимо случаев p=2, 3, примитивный элемент не уникален.

Теорема Ферма. Поведение прогрессий xk описывает широко известная в теории конечных полей и мультипликативных групп теорема Ферма (родственница великой теоремы Ферма), согласно которой xp–1=1, p – простое число. Причем при вычислении по модулю p для простых чисел всегда найдется примитивный элемент x=A, прогрессия которого займет собой все множество значений 1, ..., p–1. Заметим, что каждый ненулевой элемент конечного поля GF(p) – корень из 1, поскольку xp–1=1 для любого ненулевого элемента GF(p).

Допустим, x – не примитивный элемент. В таком случае прогрессия заканчивается раньше xn=1, где n – делитель p–1 (т.к. сохраняется и условие xp–1=1). Иллюстрация в виде строк матрицы: для не простых n, задающих вычисление по модулю, длины прогрессий xk уменьшаются (они меньше n–1), мы их можем видеть наяву, помещая в виде строк в матрицу, номер строки отвечает x, номер колонки – xk, меняя n.



Прогрессии xk для v=13 и v=15


Хорошо видно, что для GF(13) мы имеем 4 примитивных элемента, а для не простого числа v=15 ни одна прогрессия не имеет длины 15. Собственно, нет и поля с показателем 15. Максимальная длина циклической подгруппы здесь 5. Изучите прогрессии (орбиты, см. ниже) для степеней v=9 и v=27, среди них есть цепочки, регулярно прерываемые через 3. Целые числа, это не тот материал, из которого строятся GF(9) и GF(27) латанием этих дыр.

Функция Эйлера φ(n) равна количеству чисел, взаимно простых с n. Она равна p–1 для всех простых чисел n=p (мало информативна), но для не простых – уменьшается, для числа v=15 она равна 8, см. ВИКИ функция Эйлера φ(n).

Орбиты элементов, стабилизатор и фиксатор


Циклические подгруппы xk и подкольца (образуемые добавлением 0), называемые орбитами, позволяют изучить состав и характер множеств элементов входящих в мультипликативную группу кольца Z*v. Мы говорим о кольце, поскольку в орбиту включают 0.


Орбиты. Орбитой элемента m кольца Z*v называется итог масштабирования подгруппы H (подкольцо): Orb(m)=mH. Умножение на m=0 дает частную орбиту {0} (орбиту элемента 0), умножение на m=1 дает саму подгруппу H в качестве тривиальной орбиты, на m=2 – следующую частную орбиту и т.п. Частные орбиты описывают циклические подкольца кольца.

Масштабирование на элементы Z*v подгруппы H называется также действием подгруппы на кольцо. Орбита подгруппы Orb(H) – обозначение совокупности элементов всех частных орбит, ее и называют для большей простоты, орбитой H.



Подгруппы в Z*v=13, т.е. орбиты m=1 и орбиты m=2



Мы видим, что умножение на разные множители меняет значения элементов mH (элементов строк рисунков). Как обычно, интересуются неподвижными точками mh=m, h – элемент H.

Равные между собой hm=m точки (инварианты действия) можно считать по разному, в подгруппе H (замораживая m) или на множестве Z*v (замораживая h): получая элементы стабилизатора и фиксатора.

Стабилизатор. Равные в результате действия hm=m между собой элементы H образуют подгруппу в H, называемую стабилизатор Stab(m).

Фиксатор. Равные в результате действия hm=m между собой элементы Z*v образуют фиксатор элемента подгруппы Fix(h).



Классы эквивалентности H={8k} в Zv=13


Если орбиты двух элементов Z*v пересекаются, то они тождественны между собой (орбиты разбивают H на классы эквивалентности). Число классов эквивалентности (на рисунке 4) равно сумме числа стабилизаторов (их 16, если посчитать) по всем элементам группы, делённой на размер этой группы (на рисунке их 4), согласно лемме Бернсайда.

Таблицы сложения и умножения полей Галуа


Поле GF(q)=GF(pm), p – простое число, имеет q=pm элементов, нумеруемых как 0, 1, 2,..., q–1. Путь построения этого поля – оно генерируется корнем неприводимого многочлена степени m с коэффициентами из GF(p). Иными словами, в конечных конструкциях помимо "комплексной" арифметики с двумя образующими (конечного аналога комплексных чисел), существует арифметика для p образующих, оперирующая с pm значениями.

Примитивному элементу ставят в соответствие минимальный (по порядку) полином, корнем которого он является. Такой полином с коэффициентами из поля Галуа – задает связь, которая позволяет выражать старшие степени примитивного элемента через младшие. Эта техника с on line алгоритмами раскрыта ниже.


Числа – материал недостаточный (при условии, что мы не будем видеть за ними такие структуры, как полиномы, речь далее идет о "полиномиальной арифметике"), для построения полей GF(pm) с числом элементов, отличным от простого числа. Простое число p называется характеристикой сложного поля GF(pm), образованного (например) многочленами, заданными над полем GF(p) их коэффициентов, с операциями по модулю неприводимого многочлена g(x) степени m.

Многочлен X2+1 разложим в поле GF(2), поскольку (X+1)(X+1)=X2+2X+1=X2+1. Неразложим полином X2+X+1. Обозначим его корень A, ясно, что A2=–A–1=A+1 в поле GF(2). С ним мы можем построить поле GF(22) из чисел 0, 1, A, A+1, где относительно 0, 1 работают правила поля GF(2), а для уменьшения порядка итогов операции умножения с символом А привлекается правило A2=A+1 (попробуйте поскладывать и поумножать). Этого достаточно для построения таблиц сложения и умножения.

+
0
1
A
 A+1 
0
0
1
A
 A+1 
1
1
0
 A+1 
A
A
A
 A+1 
0
1
 A+1 
 A+1 
A
1
0
0
1
A
 A+1 
0
0
0
0
0
1
0
1
A
 A+1 
A
0
A
 A+1 
1
 A+1 
0
 A+1 
1
A


Элементы таблиц можно, в свою очередь, обозначить символами или кодами A=00, B=01, C=01, D=11, при таком переобозначении на первое место выступают правила, диктуемые ими. Такую таблицу проще хранить в памяти машины.

+
 00 
 01 
 11 
 10 
 00 
 00 
 01 
 11 
 10 
 01 
 01 
 00 
 10 
 11 
 11 
 11 
 10 
 00 
 01 
 10 
 10 
 11 
 01 
0
 00 
 01 
 11 
 10 
 00 
 00 
 00 
 00 
 00 
 01 
 00 
 01 
 11 
 10 
 11 
 00 
 11 
 10 
 01 
 10 
 00 
 10 
 01 
 11 



Пример 3. Попытка построить поле GF(22)=GF(4) из A=0, B=1, C=2, D=3 дает таблицы, из которых видно, что для элемента 2 по операции умножения отсутствует обратный (в таблице умножения отличных от нуля элементов появился нулевой элемент A).

+
A
B
C
D
A
A
B
C
D
B
B
A
D
C
C
C
D
A
B
D
D
C
B
A
A
B
C
D
A
A
A
A
A
B
A
B
C
D
C
A
B
A
B
D
A
D
C
B


Таблицу умножения поля GF(4) можно исправить. Над полем GF(2) есть только один неприводимый многочлен X2+X+1, соответственно, GF(4) = GF(2)[X]/X2+X+1. Пусть A=0, B=1, C=X, D=1+X. Эксплуатируя правила сложения и умножения полиномов расширенного поля, приводят следующие таблицы сложения и умножения (с точностью до символов, мы построили их ранее).

+
A
B
C
D
A
A
B
C
D
B
B
A
D
C
C
C
D
A
B
D
D
C
B
A
A
B
C
D
A
A
A
A
A
B
A
B
C
D
C
A
C
D
B
D
A
D
B
C


Первая из табличек носит название четвертной группы Клейна (классификация от 1884 г.), обозначают V4, см. WIKI. Любая перестановка элементов B,C,D не меняет этой таблицы в целом – группа переходит в себя (то есть осуществляет некоторый гомоморфизм, к тому же все перестановки обратимы, поэтому – это гомоморфизм, являющийся биекцией, то есть изоморфизм, да к тому же это еще изоморфизм группы в себя, то есть автоморфизм). При автоморфизме нейтральный элемент A всегда должен переходить в себя, поэтому никаких других автоморфизмов быть не может, S3 (симметрическая группа перестановок трех элементов) и есть искомая группа автоморфизмов, и т.п., см. заметки

Поля Галуа GF(pm)


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



Спирали аммонитов и аттрактор Пуассона


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


Резюме. Циклические группы – родственники странных аттракторов. В самом деле, чтобы породить все адамаровы базисы, которые никак не могут ни найти, ни сосчитать, надо быть достаточно странным. Нелинейность сидит в полиномиальной арифметике. У динамических систем "заварот ума" происходит ввиду явной нелинейности. А экспонента с виду безобидный продукт линейной системы. Да, но арифметика то по модулю. Подкручивающая. Вот она и блуждает. Чтобы быть циклической группой, надо, чтобы экспонента обошла все ее точки по разу. Так именно таковы и случайные аттракторы.

Приложение. Ортогональность и хаос – связанные вещи (автокорреляционная матрица белого шума ортогональна). Присмотритесь к рисунку ортогональной матрицы порядка 20 с элементами 1, –1. Число отрицательных элементов –1 циклического блока примерно вдвое меньше его порядка, их адреса в первой строке блока дает циклическая подгруппа GF(19)* соответствующего размера.



Ортогональная матрица, отвечающая подгруппе GF(19)


Поля Галуа GF(pm). Операция умножения в полиномиальной арифметике основана на свертке, которая дает примерно вдвое (менее на 1, чем вдвое) больше коэффициентов, чем нужно. Вспомогательный полином, это обратная связь, с помощью которой к коэффициентам младшей части полинома произведения прибавляются старшие. Зависимость несложна для некоторых форм вспомогательных (нередуцируемых, неприводимых) полиномов, схема полиномиального умножения напоминает нейронную. Вспомогательный полином дает веса обратных связей, желательно, чтобы большую часть ветвей ампутировали нулевые коэффициенты.



Неприводимый полином дает веса обратных связей


При обсуждении полиномиальной арифметики термин "простое число" заменяется термином "неприводимый многочлен" (нередуцируемый). Полином называется неприводимым, если его нельзя представить в виде двух других полиномов (конечно же, кроме 1 и самого полинома). Полином x2 + 1 неприводим над целыми числами, это касается также любого конечного поля. Для поля Галуа GF(pm) в качестве "модулей" используются трехчлены xm+x+1, содержат много нулевых коэффициентов.

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

Если р простое и необходимо найти все примитивные элементы поля GF(р), то достаточно найти один, а дальше возводить его в степени взаимно простые с числом p–1 – так получатся все примитивные элементы, их количество – значение функции Эйлера φ(р–1). Не занимаясь оптимизацией процесса, можно брать элемент поля наудачу (опуская квадратичные вычеты), степенная функция искомого элемента приводит обратно не ранее исчерпания размера всего поля: xр–1=1 mod p, малая теорема Ферма (для произвольного p имеем xφ(р)=1 mod p, φ(р) – количество чисел взаимно простых с р (меньших его), для простых чисел функция Эйлера φ(р)=р–1, что не возьми, все подходит).

Генератор мультипликативной группы конечного поля GF(pm) называется примитивным элементом или первообразным корнем степени pm–1, так как xpm–1=1 mod p. Примитивный многочлен над полем GF(p) именуют минимальным многочленом примитивного элемента поля GF(pm). Обзор конечных полей смотрите тут, для GF(3): x3+2x+1=0 дает x3=x+2, см. on line поиск примитивных полиномов.


Чаще всего это xm=sxd+r, при d=1 ко всем m младшим коэффициентам свертки прибавляются все старшие с множителями s, r за исключением крайних членов, к младшему коэффициенту произведения не дотягивается ветвь с весом s, к старшему коэффициенту – ветвь с весом r. При d>1 в этом простом алгоритме возникают поправки.



Потребность в s-ветви отпадает совсем для GF(p2), p – нечетное простое, произведение пары двухкомпонентных чисел (a,b)(с,d)=(aсrbd),(ad+bc). Это поле сходно с полем комплексных чисел, где –r – аналог –1 (квадрат невычета). Параметр r=2 помимо случаев r=1, p+1 кратно 4, и r=3, p+1 кратно 6. Для более сложных полей параметры задаются таблично.

 p 
 m 
 d 
 s 
 r 
2
2
1
1
1
2
3
1
1
1
2
4
1
1
1
2
5
2
1
1
2
6
1
1
1
2
7
1
1
1
2
8
5
1
1
3
3
1
1
1
3
4
1
1
1
3
5
1
1
1
3
6
1
1
1
3
7
2
1
2
3
8
2
1
1
3
9
5
1
1
5
3
1
1
1
5
4
1
1
1
5
5
1
1
1
5
6
1
1
3
5
7
1
1
2
5
8
1
0
2
 p 
 m 
 d 
 s 
 r 
7
3
1
0
2
7
4
1
1
3
7
5
1
1
3
7
6
1
0
3
7
7
1
1
1
7
8
1
1
1
7
9
1
0
2
7
 10 
1
2
1
 11 
3
1
1
3
 11 
4
1
1
6
 11 
5
1
1
1
 11 
6
1
1
1
 13 
3
1
0
2
 13 
4
1
0
2
 13 
5
1
1
1
 13 
6
1
0
2
 17 
3
1
1
2
 17 
4
1
0
3
 17 
5
1
1
6
 17 
6
1
1
4
 p 
 m 
 d 
 s 
 r 
 19 
3
1
0
2
 19 
4
1
1
1
 19 
5
1
1
3
 23 
3
1
1
4
 23 
4
1
1
3
 23 
5
1
1
2
 29 
3
1
1
1
 29 
4
1
1
1
 31 
3
1
0
3
 31 
4
1
1
1
 37 
3
1
0
2
 37 
4
1
1
1
 41 
3
1
0
2
 41 
4
1
1
7
 47 
3
1
1
1
 47 
4
1
1
1
 53 
3
1
1
4
 53 
4
1
1
2
 57 
3
1
1
8
 57 
4
1
1
5


Поиск весовых коэффициентов вспомогательного многочлена xm=sxd+r использует в качестве настройки номер алгоритма GFs=s, GFr=r, GFd=d<mпоказатель степени компоненты с параметром s. Вне таблицы [3,10,2,1,2],[3,11,2,1,2],[3,12,2,1,1][5,8,1,0,2],[5,9,4,1,4],[5,10,2,1,2],[11,7,1,1,4].

ТЕСТИРОВАНИЕ ПОЛЯ ГАЛУА МАТРИЦАМИ


Причудливый метод. Поля Галуа привлекаются для генерации (ортогональных) негациклических матриц Адамара с помощью пары показательных функций. Есть заморочка в виде "проектора" (одна из функций суммируется с собой, после "остепенения"). Сравниваемые функции "перекручиваются", как червяки. Им же не деться никуда, с поля. Точки пересечения дают –1, остальные 1. Получается бинарное описание процесса пересечения. Где скрещиваются, там на веревке из 1 бельевая защепка –1. Это и есть алгоритм генерации первой строки негациклических матриц Адамара. Генератор используется для фиксации параметров полинома, привлекаемого для построения поля. Если полином годится, то матрица синтезируется, а проверить ее ортогональность несложно.

БИБЛИОТЕКА НЕГАЦИКЛИЧЕСКИХ МАТРИЦ АДАМАРА

Пример. Разберем ниже подробнее случай xm=sxm–1+1. Обозначим как Ai, Bi усеченные до значения индекса i векторы A, B; Ak, Bk – то же самое, но компоненты взяты, напротив, с позиции k до завершения векторов (остаточные части векторов). Подчеркиванием обозначим расположение компонент в обратном порядке (флип-инверсию). Тогда формулы заметно упрощаются, первые компоненты i=0,...,m–2 рассчитываются отдельно от последней

ci=ATiBiTi+1Bi+1, cm–1Tm–1Bi+1


где Δi+1 – вектор с компонентами ATkSk, k меняется от i+1 до максимума; Sk=(s0, s1, ...) – вектор соответстующего Ak размера, зависящий от настраиваемого параметра s=2 (для полей малого размера, в табличке функции инициализации тестовой программы можно найти иные значения).

В покоординатной записи это имеет вид cik=0,iakbikk=i+1,m–1bm+ikΣj=k,m–1ajrjk, cm–1k=0,m–1bm–1–kΣj=k,m–1ajrkj.

Поля Галуа GF(p2) для нечетных p


Построение полей Галуа GF(p2) для нечетных p облегчается гарантированным наличием неприводимых многочленов вида X2r, r – квадратичный невычет (по определению). Общее число квадратичных невычетов равно (p–1)/2. Например, 2 – квадратичный невычет для p = 3, 5, 11, 13, ..., и 3 – квадратичный невычет для p = 5, 7, 17, ... .

Пусть p ≡ 3 mod 4, тогда p = 3, 7, 11, 19, ..., выбрав −1 ≡ p − 1 как квадратичный невычет, получим простой нередуцируемый многочлен X2 + 1. Следовательно, элементы вида a+jb, где j – добавляемый элемент – элементы поля GF(p2). Правила сложения и вычитания наследуют правилам комплексной арифметики. Произведение: (a,b)(с,d)=(aсrbd),(ad+bc).

Поля Галуа GF(2m)


Поле GF(2m) имеет 2m элементов, нумеруемых как 0, 1, 2,..., 2m–1. При бинарном представлении под каждое целое число требуется m бит. Биты можно использовать как коэффициенты полиномов порядка не более m–1.

Представление элементов GF(23). Элементы поля Галуа GF(23)=GF(8) можно задавать либо их индексами 0, 1, ..., 8, бинарным 000, 001, 010, ..., 111 или полиномиальным 0, 1, A, 1+A, ..., A2+A+1 представлениями.

При помощи индексов несложно задать таблицы сложения S и умножения M, отвечающих примитивному ниже полиному A3+A+1 (с помощью которого производится "возвращение" старших степеней). Сложение и умножение производится обращением к клеткам таблицы, не затрагивая полиномиальной сущности данных.

Вычислим значения примитивного полинома A3+A+1 в поле Галуа GF(8), его корни (примитивные элементы) видны в порожденном им поле. В общем случае, корни произвольного полинома размещены за пределами поля.

При работе с бинарными коэффициентами, например, характеристика поля p=2. Сложение полиномов сводится к побитовому сложению их коэффициентов по модулю 2 (ХОR), регламентирующему 1⊕1=0, т.е. при сложении x2+x с собой получим 0. При m=8 коэффициенты полинома займут байт информации. Важно, чтобы и операция умножения не выводила число коэффициентов итогового полинома за пределы этого байта.

Пример 4. Обратимся к случаю GF(23), p=2, m=3. Найдем "возвратное значение" произведения x2⊗(x2+1)=x4+x2, для чего разделим его на неприводимый полином x3+1: вычитание из x4+x2 приближающего его произведения (x3+1)x=x4+x в поле GF(2) даст остаток x2+x (обходимся без минуса). Следовательно, x2⊗(x2+1)=x2+x.

Таблица умножения может быть составлена заранее. Пометим красным маркером в таблице коэффициенты полиномов, которые мы перемножали, и соответствующий результат.

 000 
 001 
 010 
 011 
 100 
 101 
 110 
 111 
 000 
 000 
 000 
 000 
 000 
 000 
 000 
 000 
 000 
 001 
 000 
 001 
 010 
 011 
 100 
 101 
 110 
 111 
 010 
 000 
 010 
 010 
 110 
 001 
 011 
 101 
 111 
 011 
 000 
 011 
 110 
 101 
 101 
 110 
 011 
 000 
 100 
 000 
 100 
 001 
 101 
 010 
 110 
 011 
 111 
 101 
 000 
 101 
 011 
 110 
 110 
 011 
 101 
 000 
 110 
 000 
 110 
 101 
 011 
 011 
 101 
 110 
 000 
 111 
 000 
 111 
 111 
 000 
 111 
 000 
 000 
 111 


Если в качестве порождающего использован многочлен f(x), на который делится многочлен xm+1, то в этом поле умножение на x соответствует циклическому сдвигу коэффициентов. Циклические коды, возникающие здесь, используются в теории защитного кодирования.

Примечание. Для построения расширенных полей определенное значение играет алгоритм, базирующийся на алгоритме Евклида, решения уравнения at=1 mod n относительно t (мультипликативное деление).

Простое алгебраическое расширение L поля К, генерируемое корнем неприводимого многочлена X степени m, ассоциируется с кольцом остатков (quotient) K[X]/ (его элементы находятся в биективном соответствии с полиномами степени, меньшей m). Правило сложения в L – правило сложения полиномов. Правило умножения в L – итог деления на X произведения полиномов (и вот тут работает алгоритм мультипликативного деления). Реализация Евклидова деления полиномов требует карандаша-и-бумаги, что повышает вес частных более простых конструкций (и примеров).

Кодирование таблиц Кэли в пакетах


Таблицы сложения и умножения, позволяющие оперировать в полях различной сложности, называются таблицами Кэли.

В базовом MatLab для элемента 0 выбрано обозначение –Inf, остальные элементы нумеруются числами 0, 1, 2,..., q–2, что позволяет трактовать индекс как показатель степени 0, A0, A1, и т.п. (экспоненциальное представление, высшая степень ненужна, так как Aq–1=1).

Полиномиальный формат элементов имеет вид A1+A2A+...+AmAm–1, с коэффициентами, заданными в поле GF(p). В отличие от остальной практики MatLab, вектор [A1, A2, ... Am] задается в указанной последовательности.

Элементы поля GF(32) можно задавать степенями A–Inf, A0, A, ..., A7, где A – корень примитивного полинома 2+2x+x2, т.е. полинома, имеющего корень в поле 2+2A+A2=0.

Примитивный полином позволяет выразить старшие степени: A2=–2–2A, и так как коэффициенты полинома определены в поле GF(p)=GF(3), то A2=1+A. В конечном итоге имеем 0, 1, A, 1+A, 1+2A, 2, 2A, 2A+2, 2+A, которые можно записать кратко [0,0], [1,0], [0,1], [1,1], [1,2], [2,0], [0,2], [2,2], [2,1]. Отсюда путь к таблице сложения.

Данное выше поле имеет более, чем один примитивный элемент. Если два примитивных элемента имеют различные между собой минимальные полиномы, то порождаемые ими последовательности степеней различны между собой.

НАХОЖДЕНИЕ ОБРАТНОЙ МАТРИЦЫ В ПОЛЯХ ГАЛУА


Обратная матрица A–1 обобщает понятие обратного числа: AA–1=I, A–1A=I, I – единичная матрица, состоит из единиц на диагонали, прочие элементы равны нулю. Она соотносима лишь с квадратными матрицами полного ранга (невырожденными).

У ортогональных матриц обратная матрица совпадает с транспонированной матрицей (с комплексно сопряженными элементами, если речь идет о сложных полях). Обратная матрица разделяет свойства транспонированной матрицы. Правило раскрытия скобок едино для операций транспонирования и обращения (AB)'=B'A', (AB)–1=B–1A–1.

Инверсия матрицы порядка 2. В общем случае A–1 = AT/det(A), A – матрица алгебраических дополнений: у матриц второго порядка в AT элементы диагонали переставлены местами, внедиагональные элементы инвертированы по знаку, что дает простое правило ее обращения.

Простой алгоритм инверсии матрицы. Существует простой метод обращения матрицы на случай, когда диагональные элементы вычисляемой инверсной матрицы не равны 0. В противном случае потребуется перестановка строк и столбцов с усложнением алгоритма. Приведем его в силу исключительной редкости встречи в Интернет.

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

Дополнительная библиотека.


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

ИСТОРИЯ ВОЗНИКНОВЕНИЯ ПОЛЕЙ ГАЛУА


Задачи трисекции угла, удвоения куба, квадратуры круга и т.п. – древние "безнадежные" вопросы, в процессе рассмотрения которых накоплено немало полезных наблюдений. Теория конечных полей Галуа также оказалась многоплановым приобретением.

Предшественником Галуа был Лежандр, чья книга, "Теория чисел", вызвала в нем живой резонанс и интерес к теме разрешимости полиномиальных уравнений. Среди полиномиальных уравнений есть простейшие, связанные с определением корней квадратных и прочих корней (радикалов). Выход радикалов за пределы области определения коэффициентов полинома был обнаружен давно, история корня квадратного из двух насчитывает тысячелетия. Этот корень не передать отношением целых (или рациональных, все равно) чисел, т.е. радикалами более низкого порядка, корнями линейных уравнений.

Масла в огонь подлил Гаусс, старший современник Галуа. Он выразил корни уравнения x
17–1=0 всего лишь через корни квадратные, допуская возможность вложения (корень из корня).

Отсюда следует возможность вписать в круг правильный многоугольник с 17-ю сторонами с помощью циркуля и линейки, поскольку уравнения второго порядка разрешимы графически. В интернет ныне есть анимированные построения этого знаменитого многоугольника. Галуа отличился тем, что ввел (почти очевидно востребуемое для области определения не коэффициентов, а искомых решений) новое понятие конечного поля: поля коэффициентов полинома, расширенного корнями. Например, точки плоскости, до которых мы можем добраться с помощью циркуля и линейки, достаточны для построения конечного поля размерности степеней двойки. Поэтому в круг можно вписать многоугольник с 4+1=5-ю и 16+1=17-ю сторонами. А семиугольник нельзя.

Теорема Гаусса может быть интерпретирована как положение о разрешимости числа cos 2π/n в арифметике, в которой фигурируют корни квадратные, не выше, только если n=2k×(произведение чисел Ферма). Иначе эти числа неразрешимы.

Допустим, хлопоты с дефиницией радикалов – корней простейших полиномиальных уравнений – завершены их аксиоматическим определением. Кончаются ли на этом проблемы с конечностью манипуляций для достижения решений полиномиальных уравнений? Да, если поля имеют простую структуру, при которой задача поиска решения сводима к этим самым радикалам. В отличие от случая Гаусса, речь идет о радикалах более высокого порядка, с которыми мы "справились". Корни уравнения 8x3–6x+1=0 неразрешимы через корни квадратные, но на помощь приходит корень кубический. Для x5–4x+2=0 не поможет и корень пятой степени. Иерархия решений сложных уравнений высоких порядков иная, чем у уравнений до порядка 4. До Галуа это доказали Абель и Руфини.

Иными словами, для порядков 2, 3, 4 есть список приемов, при помощи которых самое общее уравнение той же степени 2, 3, 4 может быть сведено к решению нескольких вспомогательных уравнений простейшей формы. Для уравнения пятой степени этого сделать нельзя, можно доказывать, как выше, на конкретных примерах.

Исторически в этой теории возникли перестановки корней, когда осознали, что замкнутая на комплексной плоскости траектория изменения любого параметра уравнения приводит к изменению корней, имеющему параметрические точки, когда корни "ротируются" местами. Сходно ведет себя любая функция от этих корней. Радикалы, корни n-й степени, расположены симметрично на комплексной плоскости, группа их перестановок циклическая, разрешимая. Для уравнения степени пять разрешимость группы перестановок корней, в общем, приводит к противоречию, в связи с чем радикалов для их выражения недостаточно. Для разрешимости нужно вводить дополнительные уравнения, что "не страшно, но хлопотно".

У циклических матриц Адамара, корней матричного квадратного уравнения HTH=nI при ограничении элементов 1 и –1, есть сходное пороговое значение порядка: задача разрешима для матриц не выше четвертого порядка. Положение, причем, признано недоказанным.

В нынешней утвердившейся систематизации знаний, теория Галуа оперирует подстановками, элементами симметрических групп Sn, сводя задачу разрешимости полиномиальных уравнений к задаче построения цепочки вложенных друг в друга так называемых нормальных подгрупп, завершающейся тривиальной подгруппой. Для уравнения 5-го порядка группа симметрий поля, порожденного корнями многочлена, изоморфна группе вращении додекаэдра (или икосаэдра, фигуры двойственны); но у этой группы проблема с нормальными подгруппами. Если тривиальная подгруппа не достижима, значит иерархия решений уравнений сложна, среди решений есть такие, которые не выражаются через радикалы.

Это важно? Да, в общем, нет. Алгебраических конструкций – море. Одни только определения понятий занимают в обзорах солидное место, не говоря о примерах оперирования с ними. Далее нас будут интересовать не столько центральная задача, решаемая Галуа, сколько прикладные примеры на построение ортогональных матриц, с чем инструментарий, наработанный в процессе изучения групп Галуа, отлично справляется.


АРНОЛЬД | WIKI | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | ROOTS | ГРУППА | ОБЗОР

ЭКСПОНЕНТЫ И МАЯТНИКИ

Rambler's Top100