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

Yingpu Deng; Dandan Huang

doi:10.5802/jtnb.928

Explicit primality criteria for

h \cdot 2^{n} \pm 1

Yingpu Deng ¹ ; Dandan Huang ^2,¹

¹ Key Laboratory of Mathematics Mechanization, NCMIS Academy of Mathematics and Systems Science Chinese Academy of Sciences Beijing 100190, P.R. China
² (corresponding author) Laboratory of Information Security School of Software Engineering Jinling Institute of Technology Nanjing 211169, P.R. China

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

Abstract (VO)
Résumé

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

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

Reçu le : 2013-07-31
Révisé le : 2015-01-20
Accepté le : 2015-10-10
Publié le : 2017-01-02

Zbl

DOI : 10.5802/jtnb.928

Classification : 11A51, 11Y11
Keywords: Primality test, Generalized Lucasian sequence, Reciprocity Law, Computational complexity

Affiliations des auteurs :

Yingpu Deng ¹ ; Dandan Huang ^{2, 1}

¹ Key Laboratory of Mathematics Mechanization, NCMIS Academy of Mathematics and Systems Science Chinese Academy of Sciences Beijing 100190, P.R. China
² (corresponding author) Laboratory of Information Security School of Software Engineering Jinling Institute of Technology Nanjing 211169, P.R. China

@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/}
}

TY  - JOUR
AU  - Yingpu Deng
AU  - Dandan Huang
TI  - Explicit primality criteria for $h\cdot 2^n\pm 1$
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2016
SP  - 55
EP  - 74
VL  - 28
IS  - 1
PB  - Société Arithmétique de Bordeaux
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.928/
DO  - 10.5802/jtnb.928
LA  - en
ID  - JTNB_2016__28_1_55_0
ER  -

%0 Journal Article
%A Yingpu Deng
%A Dandan Huang
%T Explicit primality criteria for $h\cdot 2^n\pm 1$
%J Journal de théorie des nombres de Bordeaux
%D 2016
%P 55-74
%V 28
%N 1
%I Société Arithmétique de Bordeaux
%U https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.928/
%R 10.5802/jtnb.928
%G en
%F JTNB_2016__28_1_55_0

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/

Bibliographie
Cité par

[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 \cdot 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

Cité par Sources :