Приложения

Приложение 1. Разложение чисел вида 2^n-1 на простые множители и таблица неприводимых многочленов

В табл. А.1 содержатся разложения чисел на простые множители. В этой таблице рядом с числом стоит разложение на простые множители. Отмеченные знаком сомножители могут не быть простыми, но ни на одно простое число, меньшее 25013, они не делятся.

В табл. помещены неприводимые многочлены над в следующей записи:

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

Пример. В случае число 23 в паре (1,23) является восьмеричным представлением неприводимого многочлена над поскольку число 23 является восьмеричным представлением двоичной последовательности

В случае последовательность 112 в паре (1,112) является непосредственно последовательностью коэффициентов неприводимого многочлена

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

Для любых в таблицу помещены только неприводимые многочлены, степень которых в точности равна По этой

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

При проведении подобных вычислений удобно пользоваться таблицами циклов.

Пример. Случай

Из таблицы берем примитивный многочлен Найдем минимальные многочлены над элементов а:

1) : по таблице находим (2,101); следовательно, .

2) : так как 3 в таблицу не входит, то строим таблицу циклов:

следовательно, .

3) : аналогично строим цикл

так как этот цикл имеет длину 1, то искомый многочлен имеет степень 1.

4) : в этом случае таблица циклов имеет вид

многочленом, двойственным к является (поскольку ; значит,

5) ; следовательно,

Табл. А.1 и А.2 были построены С. Адзуми. Табл. построена с помощью а табл. — с помощью