Practical Aurifeuillian Factorization
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).
Domains
Discrete Mathematics [cs.DM]| Origin | Publisher files allowed on an open archive |
|---|
Loading...