Practical Aurifeuillian Factorization
Résumé
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).
Domaines
Mathématique discrète [cs.DM]
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...