staple
With cedram.org

Search the site

Table of contents for this issue | Previous article | Next article
Bill Allombert; Karim Belabas
Practical Aurifeuillian factorization
Journal de théorie des nombres de Bordeaux, 20 no. 3 (2008), p. 543-553, doi: 10.5802/jtnb.641
Article PDF | Reviews MR 2523308 | Zbl pre05572692

Résumé - 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)$.

Bibliography

[1] E. Bach & J. Sorenson, Explicit bounds for primes in residue classes. Math. Comp. 65 (1996), no. 216, pp. 1717–1735.  MR 1355006 |  Zbl 0853.11077
[2] 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.  MR 1344931 |  Zbl 0840.12003
[3] D. A. Burgess, On character sums and primitive roots. Proc. London Math. Soc. (3) 12 (1962), pp. 179–192.  MR 132732 |  Zbl 0106.04003
[4] H. Cohen, A course in computational algebraic number theory. Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993.  MR 1228206 |  Zbl 0786.11071
[5] A. Granville & P. Pleasants, Aurifeuillian factorization. Math. Comp. 75 (2006), no. 253, pp. 497–508.  MR 2176412 |  Zbl 1107.11050
[6] D. R. Heath-Brown, Zero-free regions for Dirichlet $L$-functions, and the least prime in an arithmetic progression. Proc. London Math. Soc. (3) 64 (1992), no. 2, pp. 265–338.  MR 1143227 |  Zbl 0739.11033
[7] H. Iwaniec, On the problem of Jacobsthal. Demonstratio Math. 11 (1978), no. 1, pp. 225–231.  MR 499895 |  Zbl 0378.10029
[8] PARI/GP, version 2.4.3, Bordeaux, 2008, http://pari.math.u-bordeaux.fr/.
[9] A. Schinzel, On primitive prime factors of $a^{n}-b^{n}$. Proc. Cambridge Philos. Soc. 58 (1962), pp. 555–562.  MR 143728 |  Zbl 0114.02605
[10] P. Stevenhagen, On Aurifeuillian factorizations. Nederl. Akad. Wetensch. Indag. Math. 49 (1987), no. 4, pp. 451–468.  MR 922449 |  Zbl 0635.10010