Practical Aurifeuillian Factorization - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Journal de Théorie des Nombres de Bordeaux Year : 2008

Practical Aurifeuillian Factorization

Bill Allombert
Karim Belabas

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).
Nous décrivons un algorithme simple pour déterminer les facteurs d’Aurifeuille des entiers Φd(a), où Φd est le d-ème polynôme cyclotomique, et a un entier. Sous une hypothèse de Riemann convenable, l’algorithme termine en temps polynomial déterministe O ̃(d2L), utilisant un espace O(dL), où l’on a noté L := log(|a| + 1).
Fichier principal
Vignette du fichier
JTNB_2008__20_3_543_0.pdf (547.5 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive
Loading...

Dates and versions

lirmm-00367227 , version 1 (04-09-2019)

Identifiers

Cite

Bill Allombert, Karim Belabas. Practical Aurifeuillian Factorization. Journal de Théorie des Nombres de Bordeaux, 2008, 20 (3), pp.543-553. ⟨10.5802/jtnb.641⟩. ⟨lirmm-00367227⟩
172 View
73 Download

Altmetric

Share

Gmail Facebook X LinkedIn More