Practical Aurifeuillian factorization
Bill Allombert[1]; Karim Belabas[2]
- [1] Université Montpellier 2 CNRS I3M/LIRMM Place Eugène Bataillon F-34095 Montpellier cedex, France
- [2] Université Bordeaux I Institut de mathématiques de Bordeaux (A2X) 351 cours de la Libération F-33405 Talence cedex, France
Journal de Théorie des Nombres de Bordeaux (2008)
- Volume: 20, Issue: 3, page 543-553
- ISSN: 1246-7405
Access Full Article
top
Abstract
topHow to cite
topAllombert, Bill, and Belabas, Karim. "Practical Aurifeuillian factorization." Journal de Théorie des Nombres de Bordeaux 20.3 (2008): 543-553. <http://eudml.org/doc/10851>.
@article{Allombert2008,
abstract = {We describe a simple procedure to find Aurifeuillian factors of values of cyclotomic polynomials $\Phi _d(a)$ for integers $a$ and $d > 0$. Assuming a suitable Riemann Hypothesis, the algorithm runs in deterministic time $\tilde\{O\}(d^2 L)$, using $O(d L)$ space, where $L \coloneqq\log (\left|a\right|+1)$.},
affiliation = {Université Montpellier 2 CNRS I3M/LIRMM Place Eugène Bataillon F-34095 Montpellier cedex, France; Université Bordeaux I Institut de mathématiques de Bordeaux (A2X) 351 cours de la Libération F-33405 Talence cedex, France},
author = {Allombert, Bill, Belabas, Karim},
journal = {Journal de Théorie des Nombres de Bordeaux},
language = {eng},
number = {3},
pages = {543-553},
publisher = {Université Bordeaux 1},
title = {Practical Aurifeuillian factorization},
url = {http://eudml.org/doc/10851},
volume = {20},
year = {2008},
}
TY - JOUR
AU - Allombert, Bill
AU - Belabas, Karim
TI - Practical Aurifeuillian factorization
JO - Journal de Théorie des Nombres de Bordeaux
PY - 2008
PB - Université Bordeaux 1
VL - 20
IS - 3
SP - 543
EP - 553
AB - We describe a simple procedure to find Aurifeuillian factors of values of cyclotomic polynomials $\Phi _d(a)$ for integers $a$ and $d > 0$. Assuming a suitable Riemann Hypothesis, the algorithm runs in deterministic time $\tilde{O}(d^2 L)$, using $O(d L)$ space, where $L \coloneqq\log (\left|a\right|+1)$.
LA - eng
UR - http://eudml.org/doc/10851
ER -
References
top- E. Bach & J. Sorenson, Explicit bounds for primes in residue classes. Math. Comp. 65 (1996), no. 216, pp. 1717–1735. Zbl0853.11077MR1355006
- R. P. Brent, Computing Aurifeuillian factors, in Computational algebra and number theory (Sydney, 1992). Math. Appl., vol. 325, Kluwer Acad. Publ., 1995, pp. 201–212. Zbl0840.12003MR1344931
- D. A. Burgess, On character sums and primitive roots. Proc. London Math. Soc. (3) 12 (1962), pp. 179–192. Zbl0106.04003MR132732
- H. Cohen, A course in computational algebraic number theory. Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. Zbl0786.11071MR1228206
- A. Granville & P. Pleasants, Aurifeuillian factorization. Math. Comp. 75 (2006), no. 253, pp. 497–508. Zbl1107.11050MR2176412
- D. R. Heath-Brown, Zero-free regions for Dirichlet -functions, and the least prime in an arithmetic progression. Proc. London Math. Soc. (3) 64 (1992), no. 2, pp. 265–338. Zbl0739.11033MR1143227
- H. Iwaniec, On the problem of Jacobsthal. Demonstratio Math. 11 (1978), no. 1, pp. 225–231. Zbl0378.10029MR499895
- PARI/GP, version 2.4.3, Bordeaux, 2008, http://pari.math.u-bordeaux.fr/.
- A. Schinzel, On primitive prime factors of . Proc. Cambridge Philos. Soc. 58 (1962), pp. 555–562. Zbl0114.02605MR143728
- P. Stevenhagen, On Aurifeuillian factorizations. Nederl. Akad. Wetensch. Indag. Math. 49 (1987), no. 4, pp. 451–468. Zbl0635.10010MR922449
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.