Explicit primality criteria for $h·2^n\pm 1$

Deng, Yingpu; Huang, Dandan

Journal de théorie des nombres de Bordeaux, Tome 28 (2016) no. 1, pp. 55-74.

Soit ${\left\{(T_k^1,...,T_k^f)\right\}}_{k\ge 0}$ 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, $k\ge 0$. Nous obtenons un algorithme ayant besoin de deux suites avec des semences convenables pour déterminer la primalité des nombres $h·2^n\pm 1$, si $h\not\equiv 0(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\pm 1$ pour tous $n$. Les techniques utilisées sont les lois de réciprocité octique et bi-octique.

Let ${\left\{(T_k^1,...,T_k^f)\right\}}_{k\ge 0}$ 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, $k\ge 0$. We describe an algorithm which needs two such sequences with two suitable seeds to determine the primality of numbers $h·2^n\pm 1$, provided $h\not\equiv 0(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\pm 1$ for all $n$. The techniques which we used are Octic and Bioctic Reciprocity Laws.

Classification : 11A51, 11Y11
Mots clés : Primality test, Generalized Lucasian sequence, Reciprocity Law, Computational complexity

[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

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

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

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

[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. | DOI | MR | Zbl

[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. | DOI | MR | Zbl

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

[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