equal_degree_factors splits a polynomial f whose factors f_i all have equal degree d over GF(q) using Cantor–Zassenhaus.
This is the basic idea. Consider a random polynomial h over GF(q) whose degree is divided by d. By the Chinese Remainder Theorem, we know GF(q)[x]/(f) is isomorphic to product of GF(q)[x]/(f_i), say via chi. The units of each factor are the units of GF(q^d).
Thus h^(q^d-1)=1. In odd characteristic on average half of the components of chi(h^(q^d-1)) are quadratic residues. Thus on average half of the components of chi(h^((q^d-1)/2) - 1) is zero. Thus there is a good chance that h^((q^d-1)/2) - 1 and f have non-trivial greatest common divisor.
This does not hold in characteristic two: all non-zero elements are quadratic residues. Instead we could use the trace.
equal_degree_factorssplits a polynomial f whose factors f_i all have equal degree d over GF(q) using Cantor–Zassenhaus.This is the basic idea. Consider a random polynomial h over GF(q) whose degree is divided by d. By the Chinese Remainder Theorem, we know GF(q)[x]/(f) is isomorphic to product of GF(q)[x]/(f_i), say via chi. The units of each factor are the units of GF(q^d).
Thus h^(q^d-1)=1. In odd characteristic on average half of the components of chi(h^(q^d-1)) are quadratic residues. Thus on average half of the components of chi(h^((q^d-1)/2) - 1) is zero. Thus there is a good chance that h^((q^d-1)/2) - 1 and f have non-trivial greatest common divisor.
This does not hold in characteristic two: all non-zero elements are quadratic residues. Instead we could use the trace.