Свободное от квадратов разложение многочлена в конечном поле
Этот калькулятор находит все повторяющиеся множители многочлена с коэффициентами в конечном поле
Этот материал распространяется на условиях лицензии Creative Commons Attribution/Share-Alike License 3.0 (Unported). Это означает, что вы можете размещать этот контент на своем сайте или создавать на его основе собственный (в том числе и в коммерческих целях), при условии сохранения оригинального лицензионного соглашения. Кроме того, Вы должны отметить автора этой работы, путем размещения HTML ссылки на оригинал работы https://planetcalc.ru/8368/. Пожалуйста оставьте без изменения все ссылки на других авторов данной работы или работы, на основе которой создана данная работа (если таковые имеются в спроводительном тексте).
Этот калькулятор находит все повторяющиеся множители многочлена с коэффициентами в конечном поле. Свободное от квадратов разложение многочлена - первый шаг в разложении многочлена на неразлагаемые множители. Более подробно можно прочитать о процедуре сразу за калькулятором.
Разложение многочлена в конечном поле свободное от квадратов
У нас уже есть похожий калькулятор для свободного от квадратов разложения полиномов в поле рациональных чисел, но он не будет работать для некоторых случаев. Алгоритм разложения на свободные от квадратов множилели основан на вычислении наибольшего общего делителя (НОД) полинома и его производной : gcd(A,A').
В кольце целых чисел или в поле рациональных производная многочлена всегда отличается от нуля. Но в конечном поле она легко может превратиться в ноль. Например, производная многочлена x6+x3+2 равна нулю в конечном поле F3, Так как (6 mod 3)x5+(3 mod 3)x2 = 0x5+0x2 = 0. Как видим, если коэффициент многочлена кратен модулю, то в производной он превращается в ноль. Если все коэффициенты многочлена кратны модулю то и сама производная равна нулю.
Алгоритм свободной от квадратов факторизации многочлена в конечном поле
Алгоритм учитывает возможность получения нулевой производной. Данный алгоритм был взят из википедии1 ( только была удалена рекурсия ):
// 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
Комментарии