Elliptic Nets
How To Catch an Elliptic Curve

Katherine Stange

USC Women in Math Seminar
November 7, 2007

http://www.math.brown.edu/~stange/

Part I: Elliptic Curves are Groups

Elliptic Curves

Frequently, we may use the simpler equation,

A Typical Elliptic Curve E

E : Y2 = X3 – 5X + 8

The lack of shame involved in the theft of this slide from Joe Silverman’s

website should make any graduate student proud.

Adding Points P + Q on E

P

Q

P+Q

R

- 5 -

The lack of shame involved in the theft of this slide from Joe Silverman’s

website should make any graduate student proud.

Doubling a Point P on E

P

2*P

R

Tangent Line to E at P

- 6 -

The lack of shame involved in the theft of this slide from Joe Silverman’s

website should make any graduate student proud.

The lack of shame involved in the theft of this slide from Joe Silverman’s

website should make any graduate student proud.

Vertical Lines and an Extra Point at Infinity

Vertical lines have no third intersection point

Q

Add an extra point O “at infinity.”

The point O lies on every vertical line.

O

P

Q = –P

Elliptic Curve Group Law

Part II: Elliptic Divisibility Sequences

Elliptic Divisibility Sequences:
Seen In Their Natural Habitat

Division Polynomials

An Elliptic Divisibility Sequence is a sequence satisfying the following recurrence relation.

Curves give Sequences

Some Example Sequences

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, …

Some Example Sequences

1, 3, 8, 21, 55, 144, 377, 987, 2584, 6765, 17711, 46368, 121393, 317811, 832040, 2178309, 5702887, 14930352, 39088169, 102334155, 267914296, 701408733, 1836311903, 4807526976, 12586269025, 32951280099, 86267571272, 225851433717, 591286729879, 1548008755920, ...

Some Example Sequences

0, 1, 1, -1, 1, 2, -1, -3, -5, 7, -4, -23, 29, 59, 129, -314, -65, 1529, -3689, -8209, -16264, 83313, 113689, -620297, 2382785, 7869898, 7001471, -126742987, -398035821, 1687054711, -7911171596, -47301104551, 43244638645, …

Our First Example

0, 1, 1, -3, 11, 38, 249, -2357, 8767, 496035, -3769372, -299154043, -12064147359, 632926474117, -65604679199921, -6662962874355342, -720710377683595651, 285131375126739646739, 5206174703484724719135, -36042157766246923788837209, 14146372186375322613610002376, …

Some more terms…

0,

1,

1,

-3,

11,

38,

249,

-2357,

8767,

496035,

-3769372,

-299154043,

-12064147359,

632926474117,

-65604679199921,

-6662962874355342,

-720710377683595651,

285131375126739646739,

5206174703484724719135,

-36042157766246923788837209,

14146372186375322613610002376,

13926071420933252466435774939177,

18907140173988982482283529896228001,

-23563346097423565704093874703154629107,

52613843196106605131800510111110767937939,

191042474643841254375755272420136901439312318,

201143562868610416717760281868105570520101027137,

-5095821991254990552236265353900129949461036582268645,

-16196160423545762519618471188475392072306453021094652577,

390721759789017211388827166946590849427517620851066278956107,

-5986280055034962587902117411856626799800260564768380372311618644,

-108902005168517871203290899980149905032338645609229377887214046958803,

-4010596455533972232983940617927541889290613203449641429607220125859983231,

152506207465652277762531462142393791012856442441235840714430103762819736595413,

-5286491728223134626400431117234262142530209508718504849234889569684083125892420201,

-835397059891704991632636814121353141297683871830623235928141040342038068512341019315446,

10861789122218115292139551508417628820932571356531654998704845795890033629344542872385904645,

13351876087649817486050732736119541016235802111163925747732171131926421411306436158323451057508131,

2042977307842020707295863142858393936350596442010700266977612272386600979584155605002856821221263113151,

-666758599738582427580962194986025574476589178060749335314959464037321543378395210027048006648288905711378993,

333167086588478561672098259752122036440335441580932677237086129099851559108618156882215307126455938552908231344016,

150866730291138374331025045659005244449458695650548930543174261374298387455590141700233602162964721944201442274446853073,

113760065777234882865006940654654895718896520042025048306493515052149363166271410666963494813413836495437803419621982027412929,

-159253169967307321375677555136314569434529937177007635953107117202675658212866813320738037987472039386883798439657624623140677934307,

44416310167318880256461428190965193979854149844320579714027500283754273952989380044808517851663079825097686172334231751637837837673262107, ...

Part III: Division Polynomials

Division Polynomials

The nth division polynomial has as zeroes the n2 n-torsion points

Therefore a sequence associated to a point of order n has Wnk = 0 for all integers k.

Division Polynomials

These are polynomials in x,y,A,B

Integer coefficients

So by a change of coordinates x → u2x, y → u3y (which implies A → u4A, B → u6B), we can obtain an integer sequence.

Curve – Sequence Correspondence

Theorem (Morgan Ward, 1948)‏

The following sets are in bijection.

(The bijection is given by explicit formulae.)‏

+

E an elliptic curve

P a point on E

P, [2]P, [3]P ≠ 0

Wn an elliptic divisibility

sequence

W1 = 1 W2W3 ≠ 0

Part IV: Reduction Mod p

Reduction of a curve mod p

0 1 2 3 4 5 6

0

1

2

3

4

5

6

(0,-3)‏

X

Reduction Mod p

0, 1, 1, 8, 0, 5, 7, 8, 0, 1, 9, 10, 0, 3, 7, 6, 0, 3, 1, 10, 0, 1,10, 8,

0, 5, 4, 8, 0, 1, 2, 10, 0, 3, 4, 6, 0, 3, 10, 10, 0, 1, 1, 8, 0, 5, 7, 8, 0, …

0, 1, 1, -3, 11, 38, 249, -2357, 8767, 496035, -3769372, -299154043,

-12064147359, 632926474117, -65604679199921, -6662962874355342,

-720710377683595651, 285131375126739646739,

5206174703484724719135, -36042157766246923788837209,

14146372186375322613610002376, …

This is the elliptic divisibility sequence associated to the curve reduced modulo 11

Zeroes of the Sequence

Reduction Mod p

0, 1, 1, 8, 0, 5, 7, 8, 0, 1, 9, 10, 0, 3, 7, 6, 0, 3, 1, 10, 0, 1,10, 8,

0, 5, 4, 8, 0, 1, 2, 10, 0, 3, 4, 6, 0, 3, 10, 10, 0, 1, 1, 8, 0, 5, 7, 8, 0, …

0, 1, 1, -3, 11, 38, 249, -2357, 8767, 496035, -3769372, -299154043,

-12064147359, 632926474117, -65604679199921, -6662962874355342,

-720710377683595651, 285131375126739646739,

5206174703484724719135, -36042157766246923788837209,

14146372186375322613610002376, …

The point has order 4, but the sequence has period 40!

The sequence is not a function of the point [n]P.

Periodicity of Sequences

Due to Morgan Ward.

Periodicity Example

0, 1, 1, 8, 0, 5, 7, 8, 0, 1, 9, 10, 0, 3, 7, 6, 0, 3, 1, 10, 0, …

Research (Partial List)‏

Applications to Elliptic Curve Discrete Logarithm Problem in cryptography (R. Shipsey)‏

Finding integral points (M. Ayad)‏

Study of nonlinear recurrence sequences (Fibonacci numbers, Lucas numbers, and integers are special cases of EDS)

Appearance of primes (G. Everest, T. Ward, …)‏

EDS are a special case of Somos Sequences (A. van der Poorten, J. Propp, M. Somos, C. Swart, …)‏

p-adic & function field cases (J. Silverman)‏

Continued fractions & elliptic curve group law (W. Adams, A. van der Poorten, M. Razar)‏

Sigma function perspective (A. Hone, …)‏

Hyper-elliptic curves (A. Hone, A. van der Poorten, …)‏

More…

Part V: Elliptic Nets: Jacking up the Dimension

The Mordell-Weil Group

From Sequences to Nets

Suppose we take the denominators of linear combinations [n]P + [m]Q of two (or n) points.

Does this array of numbers Wn,m satisfy a recurrence relation and have properties similar to those we've seen for elliptic divisibility sequences?

(Question asked by Elkies in 2001)‏

Example

249

38

11

-3

1

1

0

-149

89

7

-5

2

1

1

-1535

181

-36

-13

-1

3

1

-1466

989

-151

-41

-19

8

-5

48191

6627

493

-350

-33

53

-31

424345

68428

13751

-2591

919

479

94

-7159461

1587077

23921

-55287

12016

5959

4335

P→

↑

Q

Example

249

38

11

-3

1

1

0

-149

89

7

-5

2

1

1

-1535

181

-36

-13

-1

3

1

-1466

989

-151

-41

-19

8

-5

48191

6627

493

-350

-33

53

-31

424345

68428

13751

-2591

919

479

94

-7159461

1587077

23921

-55287

12016

5959

4335

P→

↑

Q

Example

249

38

11

-3

1

1

0

-149

89

7

-5

2

1

1

-1535

181

-36

-13

-1

3

1

-1466

989

-151

-41

-19

8

-5

48191

6627

493

-350

-33

53

-31

424345

68428

13751

-2591

919

479

94

-7159461

1587077

23921

-55287

12016

5959

4335

P→

↑

Q

Example

249

38

11

-3

1

1

0

-149

89

7

-5

2

1

1

-1535

181

-36

-13

-1

3

1

-1466

989

-151

-41

-19

8

-5

48191

6627

493

-350

-33

53

-31

424345

68428

13751

-2591

919

479

94

-7159461

1587077

23921

-55287

12016

5959

4335

P→

↑

Q

Example

249

38

11

-3

1

1

0

-149

89

7

-5

2

1

1

-1535

181

-36

-13

-1

3

1

-1466

989

-151

-41

-19

8

-5

48191

6627

493

-350

-33

53

-31

424345

68428

13751

-2591

919

479

94

-7159461

1587077

23921

-55287

12016

5959

4335

P→

↑

Q

Generalising Division Polynomials

be defined on ExE

be zero exactly when [n]P + [m]Q = 0 on the curve

be the denominator of [n]P + [m]Q up to sign.

be the usual division polynomials when (n,m) = (n,0) or (0,m)‏

ψn,m(P,Q) should...

Net Polynomials

Elliptic Nets

Define an elliptic net to be any function

satisfying

for p,q,r,s in Zn.

W: Zn → Q

Curve – Net Correspondence

Theorem (S)‏

The following sets are in bijection.

(The bijection is given by explicit formulae. Works for higher rank as well.)‏

+

E an elliptic curve

P,Q points on E

P,Q, P+Q, P-Q ≠ 0

Wn,m an elliptic net

W1,0 = W0,1 =W1,1 = 1,

W1,-1 ≠ 0

Part VI: Nets Mod p

Example

249

38

11

-3

1

1

0

-149

89

7

-5

2

1

1

-1535

181

-36

-13

-1

3

1

-1466

989

-151

-41

-19

8

-5

48191

6627

493

-350

-33

53

-31

424345

68428

13751

-2591

919

479

94

-7159461

1587077

23921

-55287

12016

5959

4335

P→

↑

Q

Example

249

38

11

-3

1

1

0

-149

89

7

-5

2

1

1

-1535

181

-36

-13

-1

3

1

-1466

989

-151

-41

-19

8

-5

48191

6627

493

-350

-33

53

-31

424345

68428

13751

-2591

919

479

94

-7159461

1587077

23921

-55287

12016

5959

4335

P→

↑

Q

Divisibility Property

Consider nets that take integer values. (By a change of coordinates, we can always obtain such a net.)‏

If W is associated to a curve E...

Example

249

38

11

-3

1

1

0

-149

89

7

-5

2

1

1

-1535

181

-36

-13

-1

3

1

-1466

989

-151

-41

-19

8

-5

48191

6627

493

-350

-33

53

-31

424345

68428

13751

-2591

919

479

94

-7159461

1587077

23921

-55287

12016

5959

4335

P→

↑

Q

Example

4

3

1

2

1

1

0

1

4

2

0

2

1

1

0

1

4

2

4

3

1

4

4

4

4

1

3

0

1

2

3

0

2

3

4

0

3

1

4

4

4

4

4

2

1

3

1

4

0

P→

↑

Q

Periodicity in two dimensions

Theorem (S)‏

Suppose r = (r1 , r2 ) such that [r1 ]P + [r2 ]Q = 0. Then there are ar , br , cr such that for all

s = (s1 , s2 ) ,

Part VII: Elliptic Curve Cryptography

Elliptic Curve Cryptography

For cryptography you need something that is

easy to do but difficult to undo.

Like multiplying vs. factoring.

Or getting pregnant.

(No one has realised any cryptographic protocols based on this:

Possible thesis topic anyone?)‏

The (Elliptic Curve) Discrete Log Problem

Let A be a group and let P and Q be known elements of A.

Hard but not too hard in Fp*.

Koblitz and Miller (1985) independently suggested using the group E(Fp) of points modulo p on an elliptic curve.

It seems pretty hard there.

The Discrete Logarithm Problem (DLP) is to find an integer m satisfying

Q = P + P + … + P = mP.

m summands

Elliptic Curve Diffie-Hellman Key Exchange

Public Knowledge: A group E(Fp) and a point P of order n.

BOB ALICE

Choose secret 0 < b < n Choose secret 0 < a < n

Compute QBob = bP Compute QAlice = aP

Compute bQAlice Compute aQBob

Bob and Alice have the shared value bQAlice = abP = aQBob

Presumably(?) recovering abP from aP and bP requires

solving the elliptic curve discrete logarithm problem.

Send QBob to Alice

to Bob Send QAlice

Yeah, I stole this one too.

The Tate Pairing

This is a bilinear pairing:

fP is the function with a pole of order

m at 0 and a zero of order m at P

independent of S

Tate Pairing in Cryptography: Tripartite Diffie-Hellman Key Exchange

Public Knowledge: A group E(Fp) and a point P of order n.

ALICE BOB CHANTAL

Secret 0 < a < n 0 < b < n 0 < c < n

Compute QAlice = aP QBob = bP QChantal = cP

Compute τn(QBob,QChantal)a τn(QAlice,QChantal)b τn(QAlice,QBob)c

These three values are equal to τn(P,P)abc

Reveal QAlice QBob QChantal

Security (presumably?) relies on Discrete Log Problem in Fp*

Part VIII: Elliptic Nets and the Tate Pairing

Tate Pairing from Elliptic Nets

Choosing a Nice Net

This is just the value of a from the periodicity relation

Calculating the Net (Rank 2)‏

Double

DoubleAdd

Based on an algorithm by Rachel Shipsey

Calculating the Tate Pairing

Find the initial values of the net associated to E, P, Q (there are simple formulae)‏

Use a Double & Add algorithm to calculate the block centred on m

Use the terms in this block to calculate

Calculating the Tate Pairing

About 100-200% of the time taken by the other known algorithm due to Victor Miller (which has been extensively optimised).

May be more efficient in certain special cases.

References

Morgan Ward. “Memoir on Elliptic Divisibility Sequences”. American Journal of Mathematics, 70:13-74, 1948.

Christine S. Swart. Elliptic Curves and Related Sequences. PhD thesis, Royal Holloway and Bedford New College, University of London, 2003.

Graham Everest, Alf van der Poorten, Igor Shparlinski, and Thomas Ward. Recurrence Sequences. Mathematical Surveys and Monographs, vol 104. American Mathematical Society, 2003.

Slides, preprint, scripts at

http://www.math.brown.edu/~stange/

<number>

Associated to a point and a curve.

Elliptic Curves and Cryptography

Elliptic Divisibility Nets