Submitted as part of 3rd year Cryptograph module (MSci Natural Sciences) to the Department of Computer Science at Durham University.

Grade: 1st Class (88%)

"Outstanding clarity, with excellent use of pseudocode, structure, and notation." "Some excellent justification of design choices." "Good critical analysis of your approach and comparison to literature."

— Coursework feedback

• submission.py - Main implementation containing the discrete logarithm solver
• RunTests.py - Test suite for validating the implementation
• report.txt - Technical report explaining the approach and design choices
• README.md - This file

python RunTests.py

This will run the test suite against the discrete logarithm solver implementation in submission.py.

To solve the discrete log problem, I used the Pohlig-Hellman algorithm with Pollard’s Rho algorithm for discrete logarithms as a subroutine.

My implementation uses three key components:

I used trial division for prime factors below 10,000 and Pollard's Rho factoring algorithm for larger factors. This hybrid approach eliminates small factors efficiently through trial division, then uses Rho for the remaining larger factors, significantly reducing computation time.

My implementation includes two key enhancements:

• Order parameter n: Extended the algorithm to work with groups of prime-power order, not just groups modulo prime p
• Hash function: set(x) = (αx + β mod p) mod 3 where α ∈ [1,n] and β ∈ [0,n] are randomly selected constants. This partitions elements into three sets for the pseudorandom function f, consistently generating almost equally-sized sets for optimal performance.

Pollard's Rho significantly outperformed Shanks' algorithm in practice, though Shanks provides stronger theoretical guarantees.

Implemented the second stage of Pohlig-Hellman to reduce subgroups of order p^c into c instances of size p. This uses the representation a = d₀p⁰ + d₁p¹ + d₂p² + ... + d_{c-1}p^{c-1} to iteratively calculate each digit d_k.

This subroutine improved time complexity from O(√p^c) to O(c√p), making computation dependent on smoothness rather than powersmoothness of p-1. This was critical for test cases where p-1 had prime powers like 2^21.

The implementation successfully solved all provided test cases within the time limits, except for one known failure case involving a 25-digit prime where p-1 is not sufficiently smooth.

Test 2.6: 25-digit prime b - Timeout (0/5 marks)

p = 3444343434443444343434443
g = 2275655143124700838125985
A = 2347678923044452300786916
Time limit: 120 seconds
Actual runtime: 230.59 seconds

True value of a: 3270347811342515980946306

This failure occurs because the Pohlig-Hellman algorithm's performance depends on the smoothness of p-1. When p-1 has large prime factors, the algorithm must solve discrete logarithm problems in large subgroups, which becomes computationally expensive. For this test case, the factorization of p-1 likely contains prime factors too large for Pollard's Rho to handle efficiently within the time constraint.