An elliptic curve test for Mersenne primes (Q1767659): Difference between revisions

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. [\textit{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), \textit{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.