Краткий план. Введение в алгебру полиномов. Наибольшие общие делители полиномов над полем (стр. 7 из 8)

Алгоритм BA (Berlecamp’s Algorithm)

Вход: Нормированный, свободный от квадратов полином

, .

Выход: Неприводимые над

сомножители полинома .

Описание реализации:

1. Построить матрицу Q.

2. Триангуляция этой матрицы. Привести матрицу Q к треугольному виду, вычислив её ранг n-r и найдя нуль-пространство (т.е. его базис

). Здесь r – число неприводимых сомножителей полинома. Так как решением уравнения сравнения являются полиномов, соответствующие векторам при любом выборе чисел . И если r=1 то полином неприводим и алгороитм завершает работу.

3. Вычисление сомножителей. Пусть

- полином, соответствующий вектору . Вычислим для всех . Если с помощью получено менее r сомножителей, вычислим для всех и всех сомножителей , найденных к данному времени, k=3,4,…,r, пока не найдётся r сомножителей. Это гарантируется предидущими теоремами.

На шаге 2 этого алгоритма матрица матрица Q приводится к треугольному виду, затрачивается время

. Так как требуется не более p вычислений НОД для каждого базисного вектора и не более r из этих вычислений будут нетривиальны, то . Так что алгоритм не очень эффективен при больших p. Разберём

Пример. Разложим над GF(13) полином

, свободный от квадратов.

Решение. Вместо данного полинома рассмотрим нормированный эквивалентный полином

.

Для начала вычислим обратные элементы ненулевым элементам GF(13) (1,…,12). Это соответственно будут (1,7,9,10,8,11,2,5,3,4,6,12).

Первая строка матрицы Q [4x4] всегда представляет собой (1,0,0,0), соответствуя полиному

. Вторая строка представляет , третья , четвёртая .

Пусть

. Предположим, что . Тогда или

. Что означает

. Здесь , .

Эти формулы объясняют вычисление

. Вычисления можно проводить используя массив . В цикле , ,…, , . Результаты отображаем в таблице:

0	0	0	0	1
1	0	0	1	0
2	0	1	0	0
3	1	0	0	0
4	9	12	11	5
5	2	2	0	6
6	7	11	2	10
7	9	8	9	9
8	11	0	4	6
9	8	6	9	3
10	0	2	0	1
11	2	0	1	0
12	5	12	9	10
13	5	4	0	12

Нетрудно видеть вторую строку матрицы Q: (12,0,4,5). Аналогично строим для k=26,39 и получаем матрицу

, .

Теперь нужно находить нуль-пространство матрицы Q-I. На основании эквивалентных преобразований матрицы составляется следующий алгоритм NS (Null-Space algorithm):

Вход: Матрица размера n

, , с элементами из поля.

Выход: Линейно независимые вектора

, такие что , n-r – ранг матрицы М.

Реализация:

1. r:=0;
   ,…,
   

2. Для h от 0 до n-1 : если найдётся столбец с номером h и

, , j=0,…,n-1, то

j-тый столбец матрицы M умножаем на

, чтобы , затем для всех прибавляем умноженный на столбец j к столбцу i. И . Если не найдётся столбца j, чтобы , то положить , выдать вектор , где для

если

, если таких k не одно, то взять любое.

если

в противном случае.

При

получится вектор . Он соответствует полиному-константе 1. При можно взять j равным 0,1,2,3, поскольку для i=1,2,3 – выбор на данном этапе полностью произволен, хотя он и влияет на получаемые при выходе векторы. Берём j=0 и после ранее описанных преобразований матрица Q имеет вид:

.

Второй элемент в первом столбце 12 – означает

. Для h=2 матрица будет

.