# Polynomial factorizaton in finite field

The calculator finds factors of a polynomial using Cantor-Zassenhaus algorithm

This calculator finds irreducible factors of an univariate polynomial in finite field using Cantor-Zassenhaus algorithm. Initially it performs Distinct degree factorization to find factors, which can be further decomposed. Finally, if required, it applies equal degree factorization algorithm described just below the calculator.

### 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 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