Practical Aurifeuillian factorization

Bill Allombert; Karim Belabas

doi:10.5802/jtnb.641

Bill Allombert ¹ ; Karim Belabas ²

¹ 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

Journal de théorie des nombres de Bordeaux, Tome 20 (2008) no. 3, pp. 543-553.

Résumé
Abstract

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 $\tilde{O} (d^{2} L)$ , utilisant un espace $O (d L)$ , où l’on a noté $L ≔ log (|a| + 1)$ .

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 $\tilde{O} (d^{2} L)$ , using $O (d L)$ space, where $L ≔ log (|a| + 1)$ .

MR

DOI : 10.5802/jtnb.641

Affiliations des auteurs :

Bill Allombert ¹ ; Karim Belabas ²

¹ 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

@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},
     mrnumber = {2523308},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.641/}
}

TY  - JOUR
AU  - Bill Allombert
AU  - Karim Belabas
TI  - Practical Aurifeuillian factorization
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2008
SP  - 543
EP  - 553
VL  - 20
IS  - 3
PB  - Université Bordeaux 1
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.641/
DO  - 10.5802/jtnb.641
LA  - en
ID  - JTNB_2008__20_3_543_0
ER  -

%0 Journal Article
%A Bill Allombert
%A Karim Belabas
%T Practical Aurifeuillian factorization
%J Journal de théorie des nombres de Bordeaux
%D 2008
%P 543-553
%V 20
%N 3
%I Université Bordeaux 1
%U https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.641/
%R 10.5802/jtnb.641
%G en
%F JTNB_2008__20_3_543_0

Bill Allombert; Karim Belabas. Practical Aurifeuillian factorization. Journal de théorie des nombres de Bordeaux, Tome 20 (2008) no. 3, pp. 543-553. doi : 10.5802/jtnb.641. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.641/

Bibliographie
Cité par

[1] E. Bach & J. Sorenson, Explicit bounds for primes in residue classes. Math. Comp. 65 (1996), no. 216, pp. 1717–1735. | MR | Zbl

[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 | Zbl

[3] D. A. Burgess, On character sums and primitive roots. Proc. London Math. Soc. (3) 12 (1962), pp. 179–192. | MR | Zbl

[4] H. Cohen, A course in computational algebraic number theory. Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. | MR | Zbl

[5] A. Granville & P. Pleasants, Aurifeuillian factorization. Math. Comp. 75 (2006), no. 253, pp. 497–508. | MR | Zbl

[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 | Zbl

[7] H. Iwaniec, On the problem of Jacobsthal. Demonstratio Math. 11 (1978), no. 1, pp. 225–231. | MR | Zbl

[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 | Zbl

[10] P. Stevenhagen, On Aurifeuillian factorizations. Nederl. Akad. Wetensch. Indag. Math. 49 (1987), no. 4, pp. 451–468. | MR | Zbl

Cité par Sources :