Explicit primality criteria for h·2 n ±1
Journal de Théorie des Nombres de Bordeaux, Tome 28 (2016) no. 1, pp. 55-74.

Soit {(T k 1 ,...,T k f )} k0 une suite de f-uplets de nombres rationnels définie à partir d’une valeur initiale : une semence (T 0 1 ,...,T 0 f ), par f relations de récurrence qui sont des polynômes à f variables déduisant le (k+1)-ième terme par le k-ième terme, k0. Nous obtenons un algorithme ayant besoin de deux suites avec des semences convenables pour déterminer la primalité des nombres h·2 n ±1, si h0(mod17), et cela en temps quasi-quadratique déterministe. En particulier, quand h=16 m -1 avec m impair, nous avons un test avec deux semences dépendant seulement de h, et pas de n, alors que les résultats de Berrizbeitia et Berry (2004) impliquent qu’aucune famille finie de semences dans leur test lucasien de primalité n’est suffisante pour tester la primalité de h·2 n ±1 pour tous n. Les techniques utilisées sont les lois de réciprocité octique et bi-octique.

Let {(T k 1 ,...,T k f )} k0 be a sequence of f-tuples of rational numbers defined from a seed (T 0 1 ,...,T 0 f ), which is a given initial value, by f recurrences which are polynomials in f variables from the k-th term to deduce the (k+1)-th term, k0. We describe an algorithm which needs two such sequences with two suitable seeds to determine the primality of numbers h·2 n ±1, provided h0(mod17), and it runs in deterministic quasi-quadratic time. In particular, when h=16 m -1,m odd, we have a test with two seeds depending only on h, not on n, while the result of Berrizbeitia and Berry (2004) implied that no finite family of seeds for their Lucasian primality test would suffice to test the primality of h·2 n ±1 for all n. The techniques which we used are Octic and Bioctic Reciprocity Laws.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : https://doi.org/10.5802/jtnb.928
Classification : 11A51,  11Y11
Mots clés : Primality test, Generalized Lucasian sequence, Reciprocity Law, Computational complexity
@article{JTNB_2016__28_1_55_0,
     author = {Yingpu Deng and Dandan Huang},
     title = {Explicit primality criteria for $h\cdot 2^n\pm 1$},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {55--74},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {28},
     number = {1},
     year = {2016},
     doi = {10.5802/jtnb.928},
     zbl = {1364.11014},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.928/}
}
Yingpu Deng; Dandan Huang. Explicit primality criteria for $h\cdot 2^n\pm 1$. Journal de Théorie des Nombres de Bordeaux, Tome 28 (2016) no. 1, pp. 55-74. doi : 10.5802/jtnb.928. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.928/

[1] B. C. Berndt, R. J. Evans & K. S. Williams, Gauss and Jacobi sums, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons, Inc., New York, 1998, A Wiley-Interscience Publication, xii+583 pages. | Zbl 0906.11001

[2] P. Berrizbeitia & T. G. Berry, « Biquadratic reciprocity and a Lucasian primality test », Math. Comp. 73 (2004), no. 247, p. 1559-1564 (electronic). | Article | MR 2047101 | Zbl 1090.11004

[3] W. Bosma, « Explicit primality criteria for h·2 k ±1 », Math. Comp. 61 (1993), no. 203, p. 97-109, S7-S9. | Article | Zbl 0817.11060

[4] K. Ireland & M. Rosen, A classical introduction to modern number theory, second ed., Graduate Texts in Mathematics, vol. 84, Springer-Verlag, New York, 1990, xiv+389 pages. | Article | Zbl 0712.11001

[5] D. H. Lehmer, « On Lucas’s Test for the Primality of Mersenne’s Numbers », J. London Math. Soc. 10 (1935), no. 3, p. 162-165. | Article | MR 1575006 | Zbl 61.0133.02

[6] E. Lucas, « Théorie des Fonctions Numériques Simplement Périodiques. [Continued] », Amer. J. Math. 1 (1878), no. 2, 3 and 4, p. 184-196, 197-240 and 289-321. | Article | MR 1505176 | Zbl 10.0134.05

[7] A. Schönhage & V. Strassen, « Schnelle Multiplikation grosser Zahlen », Computing (Arch. Elektron. Rechnen) 7 (1971), p. 281-292. | Article | Zbl 0223.68007

[8] L. C. Washington, Introduction to cyclotomic fields, second ed., Graduate Texts in Mathematics, vol. 83, Springer-Verlag, New York, 1997, xiv+487 pages. | Zbl 0966.11047

Cité par document(s). Sources :