Construction of high rankelliptic curves and related
Diophantine problems
Andrej Dujella
Department of Mathematics
University of Zagreb, Croatia
e-mail: duje@math.hr
URL: http://web.math.hr/~duje/

Let E be an elliptic curve over Q.
By Mordell’s theorem, the group E(Q) of rationals points on E is a finitely generated abeliangroup. Hence, it is the product of the torsion
group and r ≥ 0 copies of infinite cyclic group:
E(Q) ' E(Q)tors × Zr .
By Mazur’s theorem, we know that E(Q)tors is
one of the following 15 groups:Z/nZ with 1 ≤ n ≤ 10 or n = 12,
Z/2Z × Z/2mZ with 1 ≤ m ≤ 4.
On the other hand, it is not know what valuesof rank r are possible for elliptic curves over Q.
The ”folklore” conjecture is that a rank can
be arbitrary large, but it seems to be very hard
to find examples with large rank. The current
record is an example of elliptic curve over Q
with rank ≥ 28, found by Elkies in May 2006.
1

y 2 + xy + y = x3 − x2 −20067762415575526585033208209338542750930230312178956502x+34481611795030556467032985690390720374855944359319180361266008296291939448732243429

Independent points of infinite order:
P1 =[−2124150091254381073292137463,259854492051899599030515511070780628911531]
P2 =[2334509866034701756884754537,18872004195494469180868316552803627931531]
P3 =[−1671736054062369063879038663,251709377261144287808506947241319126049131]P4 =[2139130260139156666492982137,36639509171439729202421459692941297527531]
P5 =[1534706764467120723885477337,85429585346017694289021032862781072799531]
P6 =[−2731079487875677033341575063,262521815484332191641284072623902143387531]
P7 =[2775726266844571649705458537,12845755474014060248869487699082640369931]
P8 =[1494385729327188957541833817,88486605527733405986116494514049233411451]P9 =[1868438228620887358509065257,59237403214437708712725140393059358589131]
P10 =[2008945108825743774866542537,47690677880125552882151750781541424711531]
P11 =[2348360540918025169651632937,17492930006200557857340332476448804363531]
P12 =[−1472084007090481174470008663,246643450653503714199947441549759798469131]
P13 =[2924128607708061213363288937,28350264431488878501488356474767375899531]
P14 =[5374993891066061893293934537,286188908427263386451175031916479893731531]
P15 =[1709690768233354523334008557,71898834974686089466159700529215980921631]
P16 =[2450954011353593144072595187,4445228173532634357049262550610714736531]
P17 =[2969254709273559167464674937,32766893075366270801333682543160469687531]
P18 =[2711914934941692601332882937,2068436612778381698650413981506590613531]
P19 =[20078586077996854528778328937,2779608541137806604656051725624624030091531]
P20 =[2158082450240734774317810697,34994373401964026809969662241800901254731]
P21 =[2004645458247059022403224937,48049329780704645522439866999888475467531]
P22 =[2975749450947996264947091337,33398989826075322320208934410104857869131]
P23 =[−2102490467686285150147347863,259576391459875789571677393171687203227531]
P24 =[311583179915063034902194537,168104385229980603540109472915660153473931]
P25 =[2773931008341865231443771817,12632162834649921002414116273769275813451]
P26 =[2156581188143768409363461387,35125092964022908897004150516375178087331]
P27 =[3866330499872412508815659137,121197755655944226293036926715025847322531]
P28 =[2230868289773576023778678737,28558760030597485663387020600768640028531]

2

History of elliptic curves rank records:rank ≥
34
67
8
912
14
15
17
19
20
21
22
23
24
28

year
1938
1945
1974
1975
1977
1977
1982
1986
1992
1992
1992
1993
1994
1997
1998
2000
2006

Author(s)BillingWiman
Penney & Pomerance
Penney & Pomerance
Grunewald & Zimmert
Brumer - Kramer
MestreMestreMestreNagao
Fermigier
Nagao
Nagao & Kouya
FermigierMartin & McMillen
Martin & McMillen
Elkieshttp://web.math.hr/~duje/tors/rankhist.html

3

The problem of the construction of high-rank
elliptic curves has some relevance for cryptography. Namely, the discrete logarithm problemfor multiplicative group F∗q of a finite field canbe solved in subexponential time using the Index Calculus method. For this reason, it wasproposed by Miller and Koblitz in 1985 thatfor cryptographic purposes, one should replaceFq∗ by the group of rational points E(Fq ) on anelliptic curve over finite field.
DLP in F∗p:F∗p → Z; factor base F = small primes
ECDLP: E(Fp) → E(Q);factor base F = generators of E(Q)4The main reasons why Index Calculus method
cannot be applied on elliptic curves are that itis difficult:- to find elliptic curves with large rank,- to find elliptic curves generated by pointsof small height,- to lift a point of E(Fp) to a point of E(Q).

Silverman & Suzuki (1998):For p ≈ 2160, we need r ≈ 180.

5

There is even a stronger conjecture that for
any of 15 possible torsion groups T we haveB(T ) = ∞, where
B(T ) = sup{rank (E(Q)) : torsion group of E over Q is T }.

Montgomery (1987): Proposed the use of elliptic curves with large torsion group and positive rank in factorization.
It follows from results of Montgomery, Suyama,Atkin & Morain (Finding suitable curves for theelliptic curve method of factorization, 1993),that B(T ) ≥ 1 for all torsion groups T .
Womack (2000): B(T ) ≥ 2 for all T
Dujella (2003): B(T ) ≥ 3 for all T

6

B(T ) = sup{rank (E(Q)) : E(Q)tors ' T }.
The best known lower bounds for B(T ):T
0
Z/2Z
Z/3Z
Z/4Z
Z/5Z
Z/6Z
Z/7Z
Z/8Z
Z/9Z

B(T ) ≥281813126756
3

Z/10Z
Z/12Z
Z/2Z × Z/2Z
Z/2Z × Z/4Z
Z/2Z × Z/6Z
Z/2Z × Z/8Z

4314863Author(s)Elkies (06)Elkies (06)Eroshkin (07)Elkies (06)
D. & Lecacheux (01)D. (01,06), Eroshkin (07)D. & Kulesz (01), Elkies (06)Elkies (06)D. (01), MacLeod (04), Eroshkin (06),Eroshkin & Dujella (07)D. (05), Elkies (06)D. (01,05,06), Rathbun (03,06)
Elkies (05)Elkies (05)Elkies (06)Connell (00), D. (00,01,06),
Campbell & Goins (03), Rathbun (03,06),
Flores, Jones, Rollick & Weigandt (07)http://web.math.hr/~duje/tors/tors.html
7

Construction of high-rank curves
1. Find a parametric family of elliptic curves
over Q which contains curves with relatively
high rank (i.e. an elliptic curve over Q(t) withlarge generic rank).
2. Choose in given family best candidates forhigher rank. A curve is more likely to havelarge rank if #E(Fp) is relatively large for many
primes p.
3. Try to compute the rank (Cremona’s program MWRANK - very good for curves withrational points of order 2).

8G(T ) = sup{rank E(Q(t)) : E(Q(t))tors ' T }.
The best known lower bounds for G(T ):T0Z/2Z
Z/3Z
Z/4Z
Z/5Z
Z/6Z
Z/7Z
Z/8Z
Z/9Z
Z/10Z
Z/12Z
Z/2Z × Z/2Z
Z/2Z × Z/4Z
Z/2Z × Z/6Z

B(T ) ≥18
10753311000731

Z/2Z × Z/8Z

0Author(s)Elkies (2006)
Elkies (2007)
Elkies (2007)
Kihara (2004), Elkies (2007)
Lecacheux (2001)
Lecacheux (2001), Kihara (2006)
Kulesz (1998), Lecacheux (2003)
Kulesz (1998), Lecacheux (2002)
Kubert (1976)
Kubert (1976
Kubert (1976)
Elkies (2007)
Lecacheux (2001), Elkies (2007)
Kulesz (1998), Campbell (1999),
Lecacheux (2002), Dujella (2007)
Kubert (1976)

http://web.math.hr/~duje/tors/generic.html

9High-rank elliptic curves with some other additional properties:• congruent numbers: y 2 = x3 − n2 x,
r = 6, Rogers (2000)• Mordell curves: y 2 = x3 + k,r = 12, Quer (1987)• curves with j = 1728: y 2 = x3 + dx,
r = 14, Elkies & Watkins (2002)• taxicab problem: x3 + y 3 = m,r = 11, Elkies & Rogers (2004)• Diophantine triples:y 2 = (ax + 1)(bx + 1)(cx + 1)
r = 9, Dujella (2007)• Diophantine quadruples:y 2 = (ax + 1)(bx + 1)(cx + 1)(dx + 1)
r = 8, Dujella & Gibbs (2000)(published in Proc. Japan Acad.)10

A set {a1, a2, . . . , am} of m non-zero integers(rationals) is called a (rational) Diophantine
m-tuple if ai · aj + 1 is a perfect square for all
1 ≤ i < j ≤ m.
Diophantus of Alexandria:

n1 , 33 , 17 , 105
16 16 4 16oFermat: {1, 3, 8, 120}
Baker and Davenport (1969): Fermat’s set
cannot be extended to a Diophantine quintuple.
D. (2004): There does not exist a Diophantine sextuple and there are only finitely many
Diophantine quintuples.

11

Let {a, b, c} be a (rational) Diophantine triple.
Define nonnegative rational numbers q, s, t by
ab + 1 = q 2,

ac + 1 = s2,bc + 1 = t2.

In order to extend this triple to a quadruple,
we have to solve the systemax + 1 = ¤,bx + 1 = ¤,cx + 1 = ¤.

It is natural idea to assign to this system theelliptic curveE:

y 2 = (ax + 1)(bx + 1)(cx + 1).

x , y 7→ y leads toTransformation x 7→ abc
abc

E0 :

y 2 = (x + bc)(x + ac)(x + ab).

Three rational points on E 0 of order 2:
T1 = [−bc, 0],

T2 = [−ac, 0],

T3 = [−ab, 0],and also other obvious rational points
P = [0, abc],

Q = [1, qst].
12

In general, we may expect that the points P
and Q will be two independent points of infinite order, and therefore that rank E(Q) ≥2. Thus, assuming various standard conjectures, we may expect that the most of elliptic
curves induced by Diophantine triples with theabove construction will have the Mordell-Weilgroup E(Q) isomorphic to Z/2Z × Z/2Z × Z2 or
Z/2Z × Z/2Z × Z3.
Question: Which other groups are possible
here?
Mazur’s theorem: E(Q)tors = Z/2Z × Z/2mZ
with m = 1, 2, 3, 4.
D. (2001): If a, b, c are positive integers, thenthe cases m = 2 and m = 4 are not possible.
13For each 1 ≤ r ≤ 9, there exists a Diophantine
triple {a, b, c} such that the elliptic curve y 2 =(ax + 1)(bx + 1)(cx + 1) has the torsion groupisomorphic to Z/2Z × Z/2Z and the rank equal
to r.
y 2 = ((k − 1)x + 1)((k + 1)x + 1)((16k3 − 4k)x + 1)

generic rank = 2
X#E(Fp) + 1 − ps(N ) =log(p)#E(F)
pp≤N, p primes(523) > 22 & s(1979) > 33 & Selmer rank ≥ 8

k = 3593/2323, r = 9y 2 = ((k − 1)x + 1)(4kx + 1)((16k3 − 4k)x + 1)

k = −2673/491, r = 914

For each 0 ≤ r ≤ 7, there exists a Diophantine
triple {a, b, c} such that the elliptic curve y 2 =(ax + 1)(bx + 1)(cx + 1) has the torsion groupisomorphic to Z/2Z × Z/4Z and the rank equal
to r.
Curves with torsion Z/2Z×Z/4Z have the equation of the form
y 2 = x(x + α2)(x + β 2),α, β ∈ Q.

Comparison with y 2 = x(x+ac−ab)(x+bc−ab)lead to conditions ac − ab = ¤, bc − ab = ¤.
A simple way to fulfill these conditions is tochoose a and b such that ab = −1. Then ac −ab = ac + 1 = s2 and bc − ab = bc + 1 = t2.
It remains to find c such that {a, −1/a, c} is a
Diophantine triple.
Parametric solution:
8T
2T + 1, c=.
a=T −2(2T + 1)(T − 2)
T = 7995/6562, r = 715

For each 1 ≤ r ≤ 4, there exists a Diophantine
triple {a, b, c} such that the elliptic curve y 2 =(ax + 1)(bx + 1)(cx + 1) has the torsion groupisomorphic to Z/2Z × Z/6Z and the rank equal
to r.
General form of curves with the torsion groupisomorphic to Z/2Z × Z/6Z isÃ

y 2 = (x + α2)(x + β 2) x +α2β 2(α − β)2!

.

Comparison gives: α2 + 1 = bc + 1 = t2, β 2 +1 = ac+1 = s2, α2β 2 +(α−β)2 = ¤. We have:v 2 −1 , and inserting this in third,β=
α = u22u2v−1
condition we obtain the equation of the form
F (u, v) = z 2,3Parametric solution: u = vv2+v−1v = 7, r = 3u = 34/35, v = 8, r = 416

For each 0 ≤ r ≤ 3, there exists a Diophantinetriple {a, b, c} such that the elliptic curve y 2 =(ax + 1)(bx + 1)(cx + 1) has the torsion groupisomorphic to Z/2Z × Z/8Z and the rank equal
to r.
Every elliptic curve over Q with torsion group
Z/2Z × Z/8Z is induced by a Diophantine triple(D., Campbell & Goins).
Connell, D. (2000): r = 3½¾145145439408, −, −.
145
40859160

D. (2007): r = 3 (4-descent, MAGMA)½¾451352974415745765964321, −, −.
974415451352439804159080

17

Let us consider arithmetic progressions consisting of integers which are y-components ofsolutions of a Pellian equation of the form
x2 − dy 2 = m.
A. Pethő and V. Ziegler (to appear in JNT):- for the four-term arithmetic progression 1, 3, 5, 7
there exists Pellian equation x2 − dy 2 = m,where d is not a square, such that 1, 3, 5, 7 are
y-components of the solutions of this equation.
- for the arithmetic progressions 0, 1, 2, 3 suchan equation does not exist.
- for a five-terms arithmetic progression y1 <y2 < y3 < y4 < y5 (such that |yi| 6= |yj | forany i 6= j) there are at most finitely manyd, m ∈ Z such that d is not a square, m 6= 0 andgcd(d, m) is square-free such that y1, y2, y3, y4, y5
are the y-components of solutions to x2 −dy 2 =m.
18

D. & A. Pethő & P. Tadić (to appear in Acta
Math. Hungar.):- apart from 0, 1, 2, 3 and −3, −2, −1, 0, for all
four-term arithmetic progression consisting ofintegers there exist infinitely many equationsof the form x2 − dy 2 = m, where d is not asquare (if d is a square and m = 0, the problem
is trivial) and gcd(d, m) is square-free (so thatthe equations are essentially distinct) for which
the elements of the given progression form ycomponents of solutions.
- there exist arithmetic progressions with five,six and seven elements which are y-components
of solutions of a Pellian equation.

19The system
X12 − da2 = m,

X22 − d(a + k)2 = m,

X32 − d(a + 2k)2 = m,
X42 − d(a + 3k)2 = m

of Diophantine equations defines the curve ofgenus 1.
It can be transformed (T = a/k) to the ellipticcurve E:
y 2 = x3 + (176T 2 + 672T + 628)x2 + (9216T 4 + 72192T 3 + 209664T 2+ 267648T + 126720)x + 147456T 6 + 1769472T 5 + 8773632T 4+ 23003136T 3 + 33629184T 2 + 25989120T + 8294400.

Shioda’s formula ⇒ rangQ(T )E = 1.
generator:
P := [−64T 2 −256T −240, 128T 3 +640T 2 +992T +480]

e.g. rang = 7 for T = 619/6089

20

For (a, k) = (−461, 166) we obtain the ellipticcurvey 2 = x3 + 3283392x2 + 1816362270720x+ 233361525187805184
of rank 2, with generators
P1 = [2025472, 5068743680],
P2 = [−183168, 68382720].
The point P2 gives the equation
x2 + 1245y 2 = 375701326
with the property that the seven numbersa, a + k, a + 2k, a + 3k, a + 4k, a + 5k, a + 6k, i.e.
y = −461, −295, −129, 37, 203, 369, 535
are solutions of this equation.
This is the longest known arithmetic progression (with distinct absolute values) on curvesof the form x2 − dy 2 = m.
21