Skip to content

README.md

Latest commit

 

History

History
25 lines (14 loc) · 1.56 KB

README.md

File metadata and controls

25 lines (14 loc) · 1.56 KB
Raw

Using-Equivalence-Classes-to-Accelerate-Solving-the-Discrete-Logarithm-Problem-in-a-Short-Interval

Coding the 2010 paper on speeding Up Gaudry-Schost collision finding algorithm using negative endomorphisms in Python and Sage.

Abstract

This coding guide is best followed alongside this LeetArxiv article link.

Introduction

The 2010 paper Using Equivalence Classes to Accelerate Solving the Discrete Logarithm Problem in a Short Interval (Galbraith & Ruprai, 2010) introduces the Galbraith & Ruprai modification to the Gaudry-Schost collision finding algorithm for solving discrete logarithm problems in an interval in (1.36√N) field operations.

This beats the fastest Pollard-Kangaroo version (1.714√N) field operations with the caveat the Galbraith & Ruprai method is only applicable in finite fields that permit efficient endomorphisms.

The complete writeup is available here

We work with the example curve $y^2 = x^3 + 40x + 1 \pmod{3645540854261153}$ where $P = (2902755484973091, 3069996106187631)$ and the order of P is $3645540854261153$.

Getting Started

You can code alongside the Google Colab Notebook or clone the repo and run the jupyter notebook using:

git clone https://github.com/MurageKibicho/Using-Equivalence-Classes-to-Accelerate-Solving-the-Discrete-Logarithm-Problem-in-a-Short-Interval.git