Cantor–Zassenhaus algorithm: Difference between revisions

Revision as of 20:19, 25 May 2023

Revision as of 20:37, 25 May 2023

Line 8:

===Background===

The Cantor–Zassenhaus algorithm takes as input a [[square-free polynomial]] <math>f(x)</math> (i.e. one with no repeated factors) of degree ''n'' with coefficients in a finite field <math>\mathbb{F}_q</math> whose [[irreducible polynomial]] factors are all of equal degree (algorithms exist for efficiently factoring arbitrary polynomials into a product of polynomials satisfying these conditions, for instance, <math>f(x)/\gcd(f(x),f'(x))</math> is a squarefree polynomial with the same faArdithctorsfactors as <math>f(x)</math>, so that the Cantor–Zassenhaus algorithm can be used to factor arbitrary polynomials). It gives as output a polynomial <math>g(x)</math> with coefficients in the same field such that <math>g(x)</math> divides <math>f(x)</math>. The algorithm may then be applied recursively to these and subsequent divisors, until we find the decomposition of <math>f(x)</math> into powers of irreducible polynomials (recalling that the [[ring (mathematics)|ring]] of polynomials over any field is a [[unique factorisation ___domain]]).

All possible factors of <math>f(x)</math> are contained within the [[factor ring]]