Cantor–Zassenhaus algorithm: Difference between revisions

Revision as of 12:27, 19 April 2011

Revision as of 17:51, 17 May 2011

Line 1:

In [[Computational mathematics|computational]] [[Abstract algebra|algebra]], the '''Cantor–Zassenhaus algorithm''' is a well known method for factorising [[polynomial]]s over [[finite field]]s (also called Galois fields).

The algorithm consists mainly of exponentiation and polynomial [[greatest common divisor|GCD]] computations. It was invented by D. Cantor and [[Zassenhaus|Hans Zassenhaus]] in 1981.

It is arguably the dominant algorithm for solving the problem, having replaced the earlier [[Berlekamp's algorithm]] of 1967. It is currently implemented in many well-known [[computer algebra system]]s, including [[PARI/GP]].