Разложение многочлена на множители определенной степени
Калькулятор находит множители многочлена определенной степени в конечном поле
Следующий калькулятор находит множители входного полинома определенной степени в конечном поле. Также можно использовать этот калькулятор, как проверку на возможность разложения на множители (если в результате будет только один множитель, значит заданный полином не разлагаем на множители).
Если степень полученного множителя больше степени разложения, то дальнейшее разложение на множители возможно при помощи алгоритма Берлекампа или Кантора-Зассенхауза. Если степень полученного множителя совпадает со степенью разложения - этот множитель больше не разлагаем в заданном поле.
Перед началом работы этот калькулятор производит разложение на свободные от квадратов множители, если таковые находятся, то степень такого множителя будет отражена в колонке показатель.
Разложение на множители определенной степени
Алгоритм калькулятора использует известный факт, что неразлагаемый многочлен степени d будет делителем многочлена xpd-x в поле Fp, а также не будет делителем многочлена xpc-x, если 0<c<d. 1
// v(x) - свободный от квадратов входной полином
// p - модуль
w ⟵ x+0
d ⟵ 0
loop while d+1 ≤ deg(v)/2
w ⟵ w^p mod v
g ⟵ gcd( w - x, v)
if g ≠ 1 then
output ⟵ g,d
v ⟵ v / g
w ⟵ w mod v
end if
end loop
if v ≠ 1 then output ⟵ v,deg(v)
-
Дональд Кнут, Искусство программирования том 2, пар. 4.6.2 Разложение полиномов на множители ↩
Комментарии