We describe a simple procedure to find Aurifeuillian factors of values of cyclotomic polynomials for integers and . Assuming a suitable Riemann Hypothesis, the algorithm runs in deterministic time , using space, where .
Nous décrivons un algorithme simple pour déterminer les facteurs d’Aurifeuille des entiers , où est le -ème polynôme cyclotomique, et un entier. Sous une hypothèse de Riemann convenable, l’algorithme termine en temps polynomial déterministe , utilisant un espace , où l’on a noté .
@article{JTNB_2008__20_3_543_0, author = {Bill Allombert and Karim Belabas}, title = {Practical {Aurifeuillian} factorization}, journal = {Journal de Th\'eorie des Nombres de Bordeaux}, pages = {543--553}, publisher = {Universit\'e Bordeaux 1}, volume = {20}, number = {3}, year = {2008}, doi = {10.5802/jtnb.641}, zbl = {pre05572692}, mrnumber = {2523308}, language = {en}, url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.641/} }
TY - JOUR TI - Practical Aurifeuillian factorization JO - Journal de Théorie des Nombres de Bordeaux PY - 2008 DA - 2008/// SP - 543 EP - 553 VL - 20 IS - 3 PB - Université Bordeaux 1 UR - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.641/ UR - https://zbmath.org/?q=an%3Apre05572692 UR - https://www.ams.org/mathscinet-getitem?mr=2523308 UR - https://doi.org/10.5802/jtnb.641 DO - 10.5802/jtnb.641 LA - en ID - JTNB_2008__20_3_543_0 ER -
Bill Allombert; Karim Belabas. Practical Aurifeuillian factorization. Journal de Théorie des Nombres de Bordeaux, Volume 20 (2008) no. 3, pp. 543-553. doi : 10.5802/jtnb.641. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.641/
[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 -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, .
[9] A. Schinzel, On primitive prime factors of . 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
Cited by Sources: