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

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

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

Коэффициенты полинома

Модуль

Рассчитать

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

 

Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.

Загрузить 

 Ссылка  Сохранить  Виджет

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

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

Алгоритм калькулятора использует известный факт, что неразлагаемый многочлен степени d будет делителем многочлена x^pd-x в поле F_p, а также не будет делителем многочлена x^pc-x, если 0<c<d. ¹

// 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)