Cryptanalysis Project: Pollard's Rho Algorithms for Elliptic Curve Discrete Logarithm

This project implements several variants of Pollard's rho algorithm for solving the discrete logarithm problem (DLP) on elliptic curves. The implementation includes basic walks, additive walks, and an optimized version with negation maps. Given points P and Q on an elliptic curve, where Q = kP for some unknown scalar k, the goal is to efficiently find k.

Theoretical References

Primary Research Foundation:

• D. J. Bernstein, T. Lange, P. Schwabe. "On the correct use of the negation map in the Pollard rho method". 2010. https://dl.acm.org/doi/10.5555/1964658.1964669

Supporting References:

• Christophe Petit, "Cryptanalysis", Cours INFO-F514, Université libre de Bruxelles, 2025.
• Algorithms from classical cryptanalysis: Pollard's rho, additive walk, arithmetic on elliptic curves.
• Pollard's rho algorithm for logarithms – Wikipedia
• The Hare and the Hedgehog – Wikipedia
• Handbook of Applied Cryptography – Chapter 3: Number-Theoretic Reference Problems (Menezes, van Oorschot, Vanstone)

Public Repositories Consulted

• github.com/StackeredSAS/Pollard_Rho – Used as a point of reference for structural comparison and implementation on small groups.

Tools Used

• Windsurf.ai – Generate Docstring was used to generate initial docstring templates, which were then reviewed and adapted manually.
• OpenAI Codex was used to generate or assist in the drafting of basic function scaffolding, especially for helper functions and parsing logic.

Core Components

Elliptic Curve Infrastructure

• elliptic_curve.py: Standard elliptic curve operations over finite fields ℤ/pℤ
• mod128_minus3.py: Specialized arithmetic for the field ℤ/(2^128 - 3)ℤ with 10-coefficient representation

Algorithm Implementations

1. Basic Rho (basic_rho.py) : Classical Floyd's cycle detection
2. Additive Walk (additive_walk_rho.py) : Precomputed table-based walks
3. Negation Map Optimization (rho_negation_mapV2.py) : Advanced variant with fruitless cycle detection

Documentation

Detailed documentation for each algorithm is available in the docs/ directory:

• Basic Pollard's Rho
• Additive Walk Variant
• Negation Map Optimization

Prerequisites

• Python 3.8+
• matplotlib (for visualizations)
• Standard library modules: random, hashlib, time

Launch test

python3 main.py

Algorithm Comparison

Algorithm	Time Complexity	Space Complexity	Special Features
Basic Rho	O(√n)	O(1)	Simple Floyd cycle detection
Additive Walk	O(√n)	O(r)	Precomputed table, better parallelization
Negation Map	O(√n/2)	O(r)	Fruitless cycle detection, canonical forms

Where n is the order of the base point and r is the precomputed table size.