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

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

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

Anton

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

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

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 Разложение полиномов на множители 

Ссылка скопирована в буфер обмена
PLANETCALC, Разложение многочлена на множители определенной степени

Комментарии