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

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.

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.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/jtnb.928
Classification: 11A51,  11Y11
Keywords: Primality test, Generalized Lucasian sequence, Reciprocity Law, Computational complexity
Yingpu Deng 1; Dandan Huang 1, 2

1 Key Laboratory of Mathematics Mechanization, NCMIS Academy of Mathematics and Systems Science Chinese Academy of Sciences Beijing 100190, P.R. China
2 (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
TI  - Explicit primality criteria for $h\cdot 2^n\pm 1$
JO  - Journal de Théorie des Nombres de Bordeaux
PY  - 2016
DA  - 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/
UR  - https://zbmath.org/?q=an%3A1364.11014
UR  - https://doi.org/10.5802/jtnb.928
DO  - 10.5802/jtnb.928
LA  - en
ID  - JTNB_2016__28_1_55_0
ER  - 
%0 Journal Article
%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://doi.org/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, Volume 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

Cited by Sources: