An elliptic curve test for Mersenne primes. (English) Zbl 1074.11065

Let \(p=2^l-1\), \(l\) an odd prime, be the \(l\)th Mersenne number. The author first derives the Lucas-Lehmer test following ideas of M. Rosen, by showing that \(p\) is prime if and only if the image of \(\epsilon= 2+\sqrt{3}\) in the group \(({\mathbb Z}+{\mathbb{Z}}\sqrt{3}/p)^*\) has order \(2^l\). The Lucas-Lehmer test follows by looking at the traces of \(\varepsilon^{2^k}\) mod \(p\), \(0 \leq k \leq l-2\). Motivated by this, the author next shows that if \(E\) is the elliptic curve \(y^2=x(x^2-12)\) and \(P\) is the point \((2,4)\) on \(E\), (which has infinite order in \(E({\mathbb Q})\)), then the Mersenne number \(p\) is prime if and only if \(P\) has order \(2^l\) in \(E(p)\), where \(E(p)\) denotes the \({\mathbb Z}/p\)-valued points of \(E\). Taking \(x\)-coordinates of the points \(2^kP\) gives a recursively defined sequence \(\{x_k\}\) for which the following holds: if \(p\) is prime then the rational numbers \(x_k(x_k^2-1)\) are \(p\)-adic units and \(x_{l-1}\equiv 0 \) (mod \(p\)). Conversely, if the \(x_k(x_k^2-12)\) are relatively prime to \(p\) for \(0 \leq k \leq l-2\) and \(\gcd(x_{l-1},p)>1\) then \(p\) is prime.
The author asks whether these two very similar-looking tests, both involving algebraic groups, are related, and whether other tests can be developed using different algebraic groups – a challenge to the knowledgeable and astute members of the elliptic curve community. The work of P. Berrizbeitia and collaborators (including this reviewer) in fact implicitly uses other algebraic tori coming from number fields. See, e.g. [P. Berrizbeitia, B. Iskra, “Deterministic primality test for numbers of the form \(A^2. 3^n+1\), \(n \geq 3\) odd”, Proc. Am. Math. Soc. 130, No. 2, 363–365 (2002; Zbl 1006.11077), P. Berrizbeitia, T. G. Berry, J. Tena-Ayuso, “A generalization of Proth’s theorem”, Acta Arith. 110, No. 2, 107–115 (2003; Zbl 1028.11001)].
Finally, the reviewer notes that the Lucas-Lehmer test as stated in the present paper differs slightly from the standard Lucas-Lehmer test. The standard version of the test reads: define the sequence \(\{x_k\}\) by: \(x_0=2\), \(x_{k+1}=x_k^2-2\). Then \(p=2^l-1\) is prime if and only if \(x_{l-2}\equiv 0\) (mod \(p\)). As given in the paper, the test reads: if \(p\) is prime, then \(x_k \not \equiv 0\) (mod \(p\)) for \(0\leq k\leq l-3\)and \(x_{l-2} \equiv 0 \) (mod \(p\)). Conversely, if \(x_k\) is a unit \((\operatorname{mod}p)\) for \(0 \leq k \leq l-3\) and \(\gcd(x_{l-2},p)>1\), then \(p\) is prime.


11Y11 Primality


Full Text: DOI


[1] Cremona, J. E., Algorithms for Modular Elliptic Curves (1992), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0758.14042
[2] Lehmer, D. H., On Lucas’s test for the primality of Mersenne’s numbers, J. London Math. Soc., 10, 162-165 (1935) · JFM 61.0133.02
[3] Lenstra, H. W.; Pila, J.; Pomerance, C., A hyperelliptic smoothness test, II, Proc. London Math. Soc., 84, 3, 105-146 (2002) · Zbl 0983.11072
[4] Lucas, E., Nouveaux théorèmes d’Arithmétique supérieure, C. R. Acad. Sci. Paris, 83, 1286-1288 (1876) · JFM 08.0081.02
[5] Rosen, M., A proof of the Lucas-Lehmer test, American Math. Monthly, 95, 855-856 (1988) · Zbl 0669.10015
[6] Silverman, J. H., The Arithmetic of Elliptic Curves, (Graduate Texts in Mathematics, vol. 106 (1986), Springer: Springer New York) · Zbl 0979.11037
[7] Silverman, J. H., Advanced Topics in the Arithmetic of Elliptic Curves, (Graduate Texts in Mathematics, vol. 151 (1994), Springer: Springer New York) · Zbl 0911.14015
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.