|
- нетривиальное разложение полинома над GF(p).
Теперь задача состоит в определении полиномов 
. Это можно осуществить с помощью решения систем линейных уравнений, получаемой
следующим образом. Пусть
 , где коэффициенты
требуется найти. Нужно сначала проверить делит ли 
полином  . Ранее
доказано, что  .
Разделив  на 
получаем  , где 
. Теперь, заменив 
на соответствующие выражения, получим
 +[кратное ].
Таким образом  тогда и только тогда когда  делит полином
, степень которого 
. Поэтому полином степени n будет делить этот полином если только он равен нулю.
Приравняв его нулю и собрав коэффициенты при степенях х, получаем
систему из n линейных уравнений 
. Это и есть коэффициенты того полинома 
.
Пусть  - матрица, строки которой образуют
коэффициенты полиномов остатков. По этому всему имеет место
Теорема. Полином  является решением сравнения  тогда и только тогда, когда  .
Пусть N – множество векторов 
, таких что 
называется нуль-пространством матрицы 
. У этого пространства имеется базис и размерность.
Теорема. Число различных неприводимых сомножителей 
полинома  в 
равно размерности нуль-пространства матрицы 
.
Доказательство: Полином 
тогда и только тогда когда каждый 
,  . По ранее
доказанным фактам для набора 
существует единственный 
, такой что  .
Существует  решений
сравнения  . 
является решением сравнения если 
. Для вопроса о неприводимости получен
Тест3. Полином 
степени n>1 неприводим в 
тогда и только тогда когда нуль-пространство матрицы 
одномерно и  .
Доказательство: Нуль-пространство матрицы 
одномерно тогда и только тогда когда 
- степень неприводимого полинома. Тогда берём r(x)=1.
Теорема. Пусть  в 
и  - базис
нуль-пространства. Тогда для каждого 
,  , существует k 
и  , такие что 
делит, а  не делит 
.
Доказательство: В нуль-пространстве существует вектор, 
-ая компонента которой отлична от 
-ой. Значит найдётся такое k, 
,  . Положим 
.
Алгоритм BA (Berlecamp’s Algorithm)
Вход: Нормированный, свободный от квадратов полином  ,  .
Выход: Неприводимые над  сомножители полинома  .
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9
| 
