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

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

Калькулятор находит множители многочлена определенной степени в конечном поле

Следующий калькулятор находит множители входного полинома определенной степени в конечном поле. Также можно использовать этот калькулятор, как проверку на возможность разложения на множители (если в результате будет только один множитель, значит заданный полином не разлагаем на множители).

PLANETCALC, Разложение многочленов по определенным степеням

Разложение многочленов по определенным степеням

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



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

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

Алгоритм калькулятора использует известный факт, что неразлагаемый многочлен степени 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)

  1. Дональд Кнут, Искусство программирования том 2, пар. 4.6.2 Разложение полиномов на множители 

Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Разложение многочлена на множители определенной степени

Комментарии