Content deleted Content added
m Bot: Migrating 2 interwiki links, now provided by Wikidata on d:q2835780 |
m WP:CHECKWIKI error fixes - Replaced endash with hyphen in sortkey per WP:MCSTJR using AWB (9100) |
||
Line 6:
==Overview==
===Background===
The Cantor–Zassenhaus algorithm takes as input a squarefree 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 factorising arbitrary polynomials into a product of polynomials satisfying these conditions, so that the Cantor–Zassenhaus algorithm can be used to factorise 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 a finite field is a [[unique factorisation ___domain]]).
Line 78 ⟶ 79:
|doi=10.1090/S0025-5718-1981-0606517-5 }}
{{DEFAULTSORT:Cantor-Zassenhaus algorithm}}
[[Category:Computer algebra]]
[[Category:Finite fields]]
| |||