Cryptology ePrint Archive: Report 2008/444

Elliptic divisibility sequences and the elliptic curve discrete logarithm problem

Rachel Shipsey and Christine Swart

Abstract: We use properties of the division polynomials of an elliptic curve $E$ over a finite field $\mathbb{F}_q$ together with a pure result about elliptic divisibility sequences from the 1940s to construct a very simple alternative to the Menezes-Okamoto-Vanstone algorithm for solving the elliptic curve discrete logarithm problem in the case where $\#E(\mathbb{F}_q) = q-1$.

Category / Keywords: public-key cryptography / elliptic divisibility sequences, elliptic curve cryptography, elliptic curve discrete log problem

Date: received 16 Oct 2008

Contact author: christine swart at uct ac za

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20081020:192618 (All versions of this report)

Discussion forum: Show discussion | Start new discussion