Elliptic Divisibility Sequences

01/12/1999

Click here to start

Table of Contents

Elliptic Divisibility Sequences

0, 1, 1, -1, 1, 2, -1, -3, -5, 7, -4, -23, 29, 59, 129, -314, -65, 1529, -3689,

Properties of E.D.S

The Divisibility Property

?m+n ?m-n = ?m+1 ?m-1 ?n2 - ?n+1 ?n-1 ?m2

When Does p | Zm ?

Example : p=5, ?=8, ?=4

Theorem (Morgan Ward)Given a prime p and an elliptic divisibility sequence {Z}, ? integers a,b,c such that for all m,k ?Z we have

And now for something completely different……….or is it?

Elliptic Curves

Working with Elliptic Divisibility Sequences gives us a way to work with Elliptic Curves

E.D.S. Formulae

Theorem Given 4 consecutive terms of the sequence {Z} including the term Zk we can compute the term Z?k in O(log ??) multiplication steps for any given integer ?.

Example : ? = 92

The {Z} Sequence DLOG Problem

Example : ? = p

Author: MCS

Email: map01rs@gold.ac.uk

Home Page: http://homepages.gold.ac.uk/rachel/