Свободное от квадратов разложение многочлена в конечном поле

Этот калькулятор находит все повторяющиеся множители многочлена с коэффициентами в конечном поле. Свободное от квадратов разложение многочлена - первый шаг в разложении многочлена на неразлагаемые множители. Более подробно можно прочитать о процедуре сразу за калькулятором.

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

Многочлен

Модуль

Рассчитать

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

 

Решение

 

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

Загрузить 

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

У нас уже есть похожий калькулятор для свободного от квадратов разложения полиномов в поле рациональных чисел, но он не будет работать для некоторых случаев. Алгоритм разложения на свободные от квадратов множилели основан на вычислении наибольшего общего делителя (НОД) полинома и его производной : gcd(A,A').
В кольце целых чисел или в поле рациональных производная многочлена всегда отличается от нуля. Но в конечном поле она легко может превратиться в ноль. Например, производная многочлена x⁶+x³+2 равна нулю в конечном поле F₃, Так как (6 mod 3)x⁵+(3 mod 3)x² = 0x⁵+0x² = 0. Как видим, если коэффициент многочлена кратен модулю, то в производной он превращается в ноль. Если все коэффициенты многочлена кратны модулю то и сама производная равна нулю.

Алгоритм свободной от квадратов факторизации многочлена в конечном поле

Алгоритм учитывает возможность получения нулевой производной. Данный алгоритм был взят из википедии¹ ( только была удалена рекурсия ):

// a(x) - входной многочлен - должен быть моническим
// p - порядок поля
m⟵1 
do
       //вычисление НОД     
        c(x) ⟵ gcd( a(x), a'(x) ) 
        w(x) ⟵ a(x)/c(x)
       i ⟵1 
       loop while w(x) !=1 
           y(x) ⟵ gcd(w(x), c(x));
           q(x) ⟵ w(x) / y(x)
           if q(x)!=1  output ⟵ q(x)^i*m

           w(x) = y(x)
           c(x) = c(x)/y(x)
           i=i+1
       end loop
       if c(x)!=1
           a(x) = c(x)^(1/p)
           m ⟵ p*m
       end if
loop until c(x)!=1