Division Polynomials of Elliptic Curves in Python

Quick Summary

This paper introduces the elliptic divisibility sequences of an elliptic curve and their associated division polynomials.

• Here’s 20 dollars to send money abroad.

Here are some free gpu credits if you are coding along.

Stop reading papers. Start coding them. Engineers who use LeetArxiv for their professional growth can use this template email to ask their employers to expense a subscription.

As always, Google Colab notebook and GitHub available.

Abstract for the 2008 paper Elliptic Divisibility Sequences and The Elliptic Curve Discrete Logarithm Problem by Rachel Shipsey and Christine Swart

1.0 Paper Introduction

Introduction to the ECDLP problem. Taken from page 1 of (Shipsey & Swart, 2008)

The 2008 paper Elliptic Divisibility Sequences and The Elliptic Curve Discrete Logarithm Problem (Shipsey & Swart, 2008) 1 demonstrates the relationship between Elliptic Divisibility Sequences modulo a prime power and scalar multiplication on an elliptic curve.

1.1 Definitions

Elliptic curve defined over a field:

General form of an elliptic curve over a finite field. Taken from page 3 of (Shipsey & Swart, 2008)

Elliptic sequence: a sequence of rational numbers satisfying the quadratic recurrence relation (Swart, 2003) 2

Elliptic sequence. Taken from page 8 (Swart, 2003)

For every elliptic sequence (h n ) there exists an elliptic curve E and a rational point P = (x, y) such that the elliptic sequence (h n ) equals the nth division polynomial of E (ψ n ).

Elliptic sequence and division polynomials. Taken from page 8 (Swart, 2003)

Elliptic divisibility sequence (EDS): an integer elliptic sequence with the divisibility property that h n divides h m whenever n divides m. EDS are a generalization of Lucas sequences (Shipsey, 2000) 3.

Elliptic divisibility sequence. Taken from page 2 of (Shipsey & Swart, 2008)

Somos 4 sequence: a sequence of rational numbers defined by the recursion below:

Somos 4 sequence recursion. Taken from page 11 (Swart, 2003)…