Elliptic Divisibility Sequences

01/12/1999


Click here to start


Table of Contents

Elliptic Divisibility Sequences

Summary

PPT Slide

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

PPT Slide

Properties of E.D.S

The Divisibility Property

Definition

?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

PPT Slide

PPT Slide

PPT Slide

Example

Theorem

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 ?.

Proof

PPT Slide

PPT Slide

Example : ? = 92

PPT Slide

Cryptography

PPT Slide

The {Z} Sequence DLOG Problem

Example : ? = p

PPT Slide

PPT Slide

PPT Slide

PPT Slide

Summary

Author: MCS

Email: map01rs@gold.ac.uk

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