Cantor–Zassenhaus algorithm: Difference between revisions

Revision as of 20:39, 25 May 2023

Latest revision as of 11:15, 29 March 2025

(3 intermediate revisions by 3 users not shown)

Line 2:

In [[Computational mathematics|computational]] [[Abstract algebra|algebra]], the '''Cantor–Zassenhaus algorithm''' is a method for factoring [[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 [[David G. Cantor]] and [[Hans Zassenhaus]] in 1981.{{r|cz}}

It is arguably the dominant algorithm for solving the problem, having replaced the earlier [[Berlekamp's algorithm]] of 1967.{{r|Grenet}}{{r|vdh}} It is currently implemented in many [[computer algebra system]]s like [[PARI/GP]].

==Overview==

Line 49:

===Algorithm===

The Cantor–Zassenhaus algorithm computes polynomials of the same type as <math>a(x)</math> above using the isomorphism discussed in the Background section. It proceeds as follows, in the case where the field <math>\mathbb{F}_q</math> is of odd-characteristic (the process can be generalised to characteristic 2 fields in a fairly straightforward way .{{Citation neededr|reason=Not obvious for a casual reader|date=April 2022es}}). Select a random polynomial <math>b(x) \in R</math> such that <math>b(x) \neq 0, \pm 1 </math>. Set <math>m=(q^d-1)/2</math> and compute <math>b(x)^m</math>. Since <math>\phi</math> is an isomorphism, we have (using our now-established notation):

:<math>\phi(b(x)^m) = (b_1^m(x) + \langle p_1(x) \rangle, \ldots, b^m_s(x) + \langle p_s(x) \rangle).</math>

Line 59:

==Implementation in computer algebra systems==

The Cantor–Zassenhaus algorithm is implemented in the [[PARI/GP]] computer algebra system as the [http://pari.math.u-bordeaux.fr/dochtml/html-stable/Arithmetic_functions.html#factorcantorfactormod factorcantorfactormod()] function (formerly [http://pari.math.u-bordeaux.fr/dochtml/html-stable/Arithmetic_functions.html#factorcantor factorcantor()]).

==See also==

Line 66:

==References==

{{reflist|refs=

*{{citation

*<ref name=cz>{{citation

| last1 = Cantor | first1 = David G. | author1-link = David G. Cantor

| last2 = Zassenhaus | first2 = Hans | author2-link = Hans Zassenhaus

Line 78 ⟶ 80:

| title = A new algorithm for factoring polynomials over finite fields

| volume = 36| doi-access = free

}}</ref>

*http://blog.fkraiem.org/2013/12/01/polynomial-factorisation-over-finite-fields-part-3-final-splitting-cantor-zassenhaus-in-odd-characteristic/

<ref name=es>{{citation

| last1 = Elia | first1 = Michele

| last2 = Schipani | first2 = Davide

| arxiv = 1012.5322

| doi = 10.21136/mb.2015.144395

| issue = 3

| journal = Mathematica Bohemica

| pages = 271–290

| publisher = Institute of Mathematics, Czech Academy of Sciences

| title = Improvements on the Cantor–Zassenhaus factorization algorithm

| volume = 140

| year = 2015}}</ref>

<ref name=Grenet>{{citation

| last1 = Grenet | first1 = B.

| last2 = van der Hoeven | first2 = Joris | author2-link = Joris van der Hoeven

| last3 = Lecerf | first3 = G.

| date = 2016

| journal = Applicable Algebra in Engineering, Communication and Computing

| volume = 27

| pages = 237–257

| title = Deterministic root finding over finite fields using Graeffe transforms

}}</ref>

<ref name=vdh>{{citation

| last1 = van der Hoeven| first1 = Joris | author1-link = Joris van der Hoeven

| last2 = Monagan| first2 = Michael

| date = 2021

| journal = ACM Communications in Computer Algebra

| volume = 54

| issue = 3

| pages = 65–85

| title = Computing one billion roots using the tangent Graeffe method

}}</ref>

}}

==External links==

*https://web.archive.org/web/20200301213349/http://blog.fkraiem.org/2013/12/01/polynomial-factorisation-over-finite-fields-part-3-final-splitting-cantor-zassenhaus-in-odd-characteristic/

{{DEFAULTSORT:Cantor-Zassenhaus algorithm}}

[[Category:Computer algebra]]

[[Category:Finite fields]]

[[Category:PolynomialsPolynomial factorization algorithms]]