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

Deng, Yingpu¹ ; Huang, Dandan^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

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

Abstract (VO)

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.

Résumé

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.

Détail

Reçu le : 2013-08-01
Révisé le : 2015-01-21
Accepté le : 2015-10-11
Publié le : 2017-01-03
DOI : 10.5802/jtnb.928

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