homechevron_rightУчебаchevron_rightМатематикаchevron_rightАлгебра

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

Калькулятор находит множители полинома в конечном поле, используя алгоритм Кантора-Зассенхауза.

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

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

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

Входной многочлен
 
Решение
 

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

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

  • Убедиться, что входной полином свободен от квадратов
  • Найти все множтели различных степеней
  • Выполнить разложение множителей одной степени, приведенное ниже, для множителя заданной степени, полученного на предыдущем шаге. Например, в ходе разложения по различным степеням получен полином x2+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
Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Факторизация полинома в конечном поле

Комментарии