Polynomial factorization in a finite field
The calculator finds factors of a polynomial using Cantor-Zassenhaus algorithm
This page exists due to the efforts of the following people:
Anton
| |
 | Timur
|
This content is licensed under Creative Commons Attribution/Share-Alike License 3.0 (Unported). That means you may freely redistribute or modify this content under the same license conditions and must attribute the original author by placing a hyperlink from your site to this work https://planetcalc.com/8372/. Also, please do not modify any references to the original work (if any) contained in this content.
This calculator finds irreducible factors of a univariate polynomial in the finite field using the Cantor-Zassenhaus algorithm. Initially, it performs Distinct degree factorization to find factors, which can be further decomposed. Finally, if required, it applies an equal degree factorization algorithm described just below the calculator.
Cantor-Zassenhaus polynomial factorizaton in finite field
Cantor-Zassenhaus factorization algorithm
This algorithm generally has better characteristics for big modulus than similar Berlecamp factorization algorithm.
- Check the polynomial is square-free
- Find all factors for distinct degrees
- Apply equal degree decomposition algorithm, described below, for every factor which degree greater than distinct degree obtained on the previous step
Equal degree factorization algorithm
// u(x) - Input polynomial of degree rd
// which has r factors each
// of degree d in Fp field
// p - odd field order
// d - target factors degree
// r - number of target factors
s⟵ { u }
loop while size(s) less than r
h ⟵ random polynomial
of degree less than 2d
g ⟵ h^(p^d-1/2) -1 mod u
for each a in s do
if deg(a) greater than d
and gcd(g, a) ≠ 1
and gcd(g, a) ≠ a then
remove a from s
add gcd(g,a) to s
add a/gcd(g,a) to s
end if
end do
end loop
output s
Comments