The Discrete Logarithm Problem

This paper discusses the discrete logarithm problem both in general and specifically in the multiplicative group of integers modulo a prime. Various so called "square-root" attacks are discussed for the discrete logarithm problem in an arbitrary cyclic group. Then the index calculus method and the number field sieve method for solving discrete logarithms modulo a prime are introduced and their run-time is analyzed. Finally, implementations of the index calculus method and the number field sieve were created and graphs of their performance are presented.

This paper was written to satisfy the research paper requirement (milestone) of the PhD program at the University of Toronto.

The paper is available for download here in both PDF format (424KiB) and Postscript format (504KiB).

Some of the source code for this project is available below and licenced under the General Public Licence. All of the source code for this project will eventially be released. If you need some of the code described in the paper above and it's not posted below, let me know and I'll do my best to get you the code.

Note: the code releases below may be out of date. Please see my GitHub account for the most up-to-date versions of this software.

Code for computing discrete logarithms in the multiplicative group of GF(p), p prime, using the index calculus method of Coppersmith, Odlzyko, and Schroeppel is available in dlog-1.2.tar.gz (50.3 KiB). If your interest is in the computation of discrete logarithms for some other project, and your modulus, p, is no larger than about 120 bits, then this index calculus code is as fast and more robust than my number field sieve code.

If you are interested in developing software implementing the number field sieve (NFS) algorithm of solving discrete logarithms, or if you just want to learn about the NFS algorithm, you may be interested in my implemenation. It is available in dlog-nfs-1.1.tar.gz (58.6KiB). Please note that this implementation of the NFS algorithm fails often.

Also available here is code for factoring integers using Lenstra's Elliptic Curve Method (ECM). This code was not developed as a part of the discrete logarithm work above, but it can be used to speed up some of the smoothness tests done in the discrete logarithm methods. The code is in ecm-1.01.tar.gz (20.4KiB). It can be used to find factors as large as 100 bits in a matter of hours on a typical PC.

And finally, I also have an implementation of an elliptic curve primality proof (ECPP) algorithm. It is available in ecpp-1.01.tar.gz (36.7KiB). This implementation works reasonably well for primes up to about 1000 bits in size, but it is not yet developed to the point where it should be used to actually prove primes (although it can do that). Like the NFS code above, this release is really targetted at developers or students interested in ECPP.

 


Last modified: 9-June-2013
by Chris Studholme
Chris's Home Page