Факторизация полинома в конечном поле
Калькулятор находит множители полинома в конечном поле, используя алгоритм Кантора-Зассенхауза.
Этот материал распространяется на условиях лицензии Creative Commons Attribution/Share-Alike License 3.0 (Unported). Это означает, что вы можете размещать этот контент на своем сайте или создавать на его основе собственный (в том числе и в коммерческих целях), при условии сохранения оригинального лицензионного соглашения. Кроме того, Вы должны отметить автора этой работы, путем размещения HTML ссылки на оригинал работы https://planetcalc.ru/8372/. Пожалуйста оставьте без изменения все ссылки на других авторов данной работы или работы, на основе которой создана данная работа (если таковые имеются в спроводительном тексте).
Этот калькулятор находит все неразлагаемые множители полинома одной переменной в конечном поле, используя алгоритм Кантора-Зассенхауза. Первоначально калькулятор выполняет Разложение по различным степеням для нахождения множителей. Далее, если требуется для множителей, полученных на предыдущем шаге, выполняется разложение множителей конкретной степени, описание этого алгоритма можно найти сразу за калькулятором.
Разложение многочлена на множители методом Кантора-Зассенхауза
Алгоритм факторизации Кантора-Зассенхауза
Данный алгоритм обладает лучшими характеристиками, чем факторизация методом Берлекампа для больших модулей 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
Комментарии