Elliptic curve primality tests for Fermat and related primes
type: Item
instance of: scholarly article
title: Elliptic curve primality tests for Fermat and related primes
zbMATH Open document ID: 1196.11168
author: Robert Denomme
author: Gordan Savin
published in: Journal of Number Theory
publication date: 2009-06-17T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 11Y11
Mathematics Subject Classification ID: 11A51
Mathematics Subject Classification ID: 11G15
Mathematics Subject Classification ID: 11G05
zbMATH DE Number: 5565656
zbMATH Keywords: primality tests
zbMATH Keywords: Fermat primes
zbMATH Keywords: elliptic curves
zbMATH Keywords: complex multiplication
zbMATH Keywords: twisted curves
reviewed by: Juan Tena Ayuso
MaRDI profile type: Publication
full work available at URL: j.jnt.2007.12.009
OpenAlex ID: W2049949199
cites work: Q4423053
cites work: An elliptic curve test for Mersenne primes
cites work: Q3999066
DOI: 10.1016/J.JNT.2007.12.009
description: scientific article; zbMATH DE number 5565656