Факторизация полинома в конечном поле

Этот калькулятор находит все неразлагаемые множители полинома одной переменной в конечном поле, используя алгоритм Кантора-Зассенхауза. Первоначально калькулятор выполняет Разложение по различным степеням для нахождения множителей. Далее, если требуется для множителей, полученных на предыдущем шаге, выполняется разложение множителей конкретной степени, описание этого алгоритма можно найти сразу за калькулятором.

Разложение многочлена на множители методом Кантора-Зассенхауза

Коэффициенты полинома

Модуль

Детали

Рассчитать

Входной многочлен

 

Решение

 

Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.

Загрузить 

Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.

Загрузить 

 Ссылка  Сохранить  Виджет

Алгоритм факторизации Кантора-Зассенхауза

Данный алгоритм обладает лучшими характеристиками, чем факторизация методом Берлекампа для больших модулей p.

• Убедиться, что входной полином свободен от квадратов
• Найти все множтели различных степеней
• Выполнить разложение множителей одной степени, приведенное ниже, для множителя заданной степени, полученного на предыдущем шаге. Например, в ходе разложения по различным степеням получен полином x²+10x+8 для степени 1, для этого полинома возможно разложение на два линейных множителя следующим алгоритмом.

  Разложение на множители одной степени

// u(x) - Входной полином степени rd, 
//   который содержит r множителей 
//   степени d в поле Fp 
// p - нечетный порядок поля (модуль)
// d - степень множителей результата разложения
// r - количество множителей результата разложения
// в наборе множителей сохранить 
//    начальный полином
s⟵ { u } 
выполнять цикл до тех пор,
 пока размер набора s меньше r
        h ⟵ случайный многочлен степени 2d
        g ⟵ h^(p^d-1/2) -1 mod u
        для каждого элемента a набора s выполнить 
              если deg(a) > d 
             и gcd(g, a) ≠ 1 
             и gcd(g, a) ≠ a тогда
                   удалить a из набора s
                   добавить gcd(g,a) в набор s
                   добавить a/gcd(g,a) в набор s
              конец условия
         конец цикла
конец цикла
результат - набор s