Skip to Main content Skip to Navigation
Journal articles

Practical Aurifeuillian Factorization

Bill Allombert 1 Karim Belabas 2
1 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We describe a simple procedure to find Aurifeuillian factors of values of cyclotomic polynomials Φd(a) for integers a and d > 0. Assuming a suitable Riemann Hypothesis, the algorithm runs in deterministic time O ̃(d2L), using O(dL) space, where L := log(|a| + 1).
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00367227
Contributor : Martine Peridier <>
Submitted on : Wednesday, September 4, 2019 - 8:28:28 PM
Last modification on : Thursday, February 13, 2020 - 1:14:04 AM
Document(s) archivé(s) le : Thursday, February 6, 2020 - 3:46:00 AM

File

JTNB_2008__20_3_543_0.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : lirmm-00367227, version 1

Collections

Citation

Bill Allombert, Karim Belabas. Practical Aurifeuillian Factorization. Journal de Théorie des Nombres de Bordeaux, Société Arithmétique de Bordeaux, 2008, 20 (3), pp.543-553. ⟨lirmm-00367227⟩

Share

Metrics

Record views

165

Files downloads

60