Cantor–Zassenhaus algorithm: Difference between revisions

Revision as of 08:50, 24 July 2024

Latest revision as of 11:15, 29 March 2025

Line 4:

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 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 94:

| 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==