10. Вычисления в конечных полях
Со всех сторон выползают монстры - новые спорадические простые группы,которым не видно конца и существование которых устанавливается зачастую при помощи новейших ЭВМ.
А.И.Кострикин. Введение к сб. К теории конечных групп, 1979.
Конечные поля рассмотрены в книге [4, 4.4.6, 9.1], перестановки - в [4, 4.2.4].
Поле называется конечным, если оно состоит из конечного количества элементов. Для любого простого числа р и любого натурального числа n существует поле, состоящее из р^n элементов. В данном параграфе мы рассмотрим поля, состоящие из р элементов, в п.13 - произвольные конечные поля.
Множество Zn классов вычетов по модулю n образует кольцо. Если р - простое число, то Zp образует поле, т.е. в нем можно производить сложение, вычитание, умножение и деление. Мы будем работать со следующими представителями смежных классов:
0, 1, 2, ... , р-1 .
Рассмотрим в поле Z11 несколько примеров операций.
2 + 10 = 1, так как 2 + 10 = 12 = 1 (mod 11)
2 х 10 = 9, так как 2 х 10 = 20 = 9 (mod 11)
2^(-1) = 6, так как 2 х 6 = 12 = 1 (mod 11 )
5^(-1) = 9, так как 5 х 9 = 45 = 1 (mod 11)
Элементы поля Zp будем представлять в виде целых чисел, т.е. в виде последовательности макроцифр.
Нашей задачей является написание функций, осуществляющих операции в поле Zp . Поскольку эти функции могут понадобиться в других программах, то мы оформим их в виде отдельного модуля. Текст этого модуля приведем в z_p.ref. Мы опишем следующие функции:
Zp_Add - сложение в поле Zp ,
Zp_Sub - вычитание в поле Zp ,
Zp_Mul - умножение в поле Zp ,
Zp_Inv - нахождение обратного элемента по умножению в поле Zp ,
Zp_Div - деление в поле Zp .
Теперь надо обсудить формат обращения к этим функциям. Результат операции, например, сложения, зависит от слагаемых и от простого числа р. Поэтому можно было бы выбрать такой формат обращения к функции
<Zp_Add (e.M) (e.N) e.P >
где е.М, e.N - слагаемые, е.Р - простое число.
Этот формат неудобен по следующим причинам. Когда происходит много различных вычислений, то значение еР должно будет присутствовать во всех преобразованиях поля зрения.
Поэтому хотелось бы иметь форматы обращения к функциям Zp_Add, Zp_Sub, ... такие же, как и для арифметических функций Рефала ADD, SUB, ... .
Каким способом получить значение числа p при вычислениях? Одним из способов является использование копилки.
Итак, предлагается следующий режим работы с арифметическими функциями в поле Zp. Перед самым первым обращением к этим функциям необходимо закопать число р в копилке под именем "Р" т.е. выполнить <BR 'P=' e.P>, где е.Р - простое число р, представленное в виде последовательности макроцифр.
Например, для поля Z11 пишем
<BR 'P=' 11 >
Формат обращения к функциям следующий:
<D (e.M) e.N >
если D совпадает с одним из имен Zp_Add, Zp_Sub, Zp_Mul, Zp_Div, или
<Zp_Inv e.M >
где е.М, e.N - целые неотрицательные числа меньшие, чем е.Р.
Результат замены - целое число, являющееся результатом соответствующей операции в поле Zp .
Сделаем пояснения к z_p.ref, где изображены функции модулярной арифметики.
Функция МОД находит остаток от деления аргумента на число р.
Сложение и умножение описываются очевидным образом.
Функция Divmod выдает остаток отрицательным, если делимое отрицательно. Поэтому, чтобы не делать проверок на знак остатка, мы в функции Zp_Sub сразу прибавляем е.Р к первому операнду.
Функция Zp_Div сводит деление к умножению на обратный элемент.
Наиболее сложной оказывается функция Zp_Inv.
Так как m и р взаимно простые числа, то НОД(m,p) = 1 , поэтому
1 = u х m + v х p
для некоторых целых чисел u, v. Переходя к полю Zp, получаем u х m = 1, поэтому u = m^(-1) .
Для практического нахождения m используем следующее замечание.
Если
A = X х M (mod p)
B = Y х M (mod p), и
A = Q х B + R, то
R = ( X - Y х Q ) х M (mod p)
Мы начинаем с двух очевидных сравнений
р = 0 х M (mod p)
M = 1 х M (mod p)
Затем применяем последовательные деления из алгоритма Евклида и получаем для некоторого u
1 = U х M (mod p)
Поскольку для получения U мы работаем по модулю р, то все операции можно производить в поле Zp .
Функция Zp_Inv делает первый шаг и подготавливает аргумент для функции Zp_Inv1. B первой скобке находится значение A, во второй - X, в третьей - B, в четвертой - Y.
(*)З А Д А Ч А. Выражением GL(n,p) обозначают группу невырожденных матриц размера n х n c коэффициентами из поля Zp . Напишите функции для вычислений в группе GL(n,p): умножение матриц, обращение матрицы, вычисление определителя матрицы, приведение матрицы к треугольному виду и т.д. Отметим, что все вычисления в группе GL(n,p) осуществляются точно, поэтому нет необходимости применять такие методы вычислительной линейной алгебры, как выбор главного элемента и т.д.