Elliptic curve primality tests for Fermat and related primes (Q1024418): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Juan G. Tena Ayuso / rank | |||
Property / reviewed by | |||
Property / reviewed by: Juan G. Tena Ayuso / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.jnt.2007.12.009 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2049949199 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4423053 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An elliptic curve test for Mersenne primes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3999066 / rank | |||
Normal rank |
Latest revision as of 16:47, 1 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Elliptic curve primality tests for Fermat and related primes |
scientific article |
Statements
Elliptic curve primality tests for Fermat and related primes (English)
0 references
17 June 2009
0 references
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).
0 references
primality tests
0 references
Fermat primes
0 references
elliptic curves
0 references
complex multiplication
0 references
twisted curves
0 references