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

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

Эта страница существует благодаря следующим персонам

Anton

Создан: 2019-09-08 13:04:14, Последнее изменение: 2020-11-03 14:19:37

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

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
Ссылка скопирована в буфер обмена
PLANETCALC, Факторизация полинома в конечном поле

Комментарии