Elliptic curve primality tests for Fermat and related primes (Q1024418)

Motivated by an elliptic test for Mersenne primes due to \textit{B. H. Gross} [J. Number Theory 110, No. 1, 114--119 (2005; Zbl 1074.11065)] the paper shows an alternative, based on elliptic curves, to the classical Pepin's primality test for Fermat numbers \(F_l=2^{2^l}+1\)\, and extents it to numbers of the form \(J_l=2^{2^l}-2^{2^{l-1}}+1\)\, and \(K_l=3^{2^l}-3^{2^{l-1}}+1\). The proposed test for the family of numbers \(F_l\)\, uses the elliptic curve \(E: y^2=x^3-x\),\, with \(Z[i]\)\, as endomorphism ring. As the paper points out, over the finite field \(k=\mathbb{F}_{F_l}\)\, (\(F_l\)\, supposed to be prime), the group \(E(k)\)\, has order \(2^{2^l}\)\, (the same as the multiplicative group \(k^*\)\, used in Pepin's test). Instead of \(E\)\, the test takes its quadratic twist \(E_{30}: 30y^2=x^3-x\)\, which, \(30\)\, been a square in \(k\),\, is isomorphic to \(E\). Proposition 4 shows the isomorphism of \(Z[i]\)-modules \(E(k)\simeq Z[i]/(1+i)^{2^l}\)\, and proposition 5 proves that the point \(P=(5,2)\)\, is a generator of the \(Z[i]\)-module \(E_{30}\). Section 4 gives the desired test in terms of \(P\)\, and then deduces a version in terms of a sequence of Gaussian integers in a way similar to the classical Lucas-Lehmer test for Mersenne numbers. Although the paper does not study the complexity of the proposed test it is obvious that it needs \(O(2^l)\)\, modular elementary operations, the same that Pepin's test (although this last one is faster). However the proposal has the advantage of being generalizable to other families of numbers. The paper proposes then similar tests for the numbers \(J_l\)\, and \(K_l\),\, using the elliptic curve \(y^2= x^3+D/4\)\, which, for appropriate D, has order \(2^{2^l}\)\, and \(3^{2^l}\)\ over \(\mathbb{F}_{J_l}\)\, and \(\mathbb{F}_{K_l}\)\, respectively (\({J_l}\),\, \({K_l}\)\, supposed to be primes).