A Study of the Parallelism and Efficiency of the Index Calculus Algorthim

Michael Pratt
Capstone Project of CS Master's Program

Defense: November 14, 2011

Modern public-key cryptosystems rely on the infeasibility of computing discrete logarithms on sufficiently large finite groups. Any reasonable effort to attack such a cryptosystem would require a sophisticated parallel algorithm and substantial computing resources.

The goal of this project is to implement a parallelized version of the index calculus algorithm and observe its ability to solve comparatively small discrete logs. Of primary interest is how some of the algorithm's parameters can affect the algorithm's scalability - that is, how computation time scales with the amount of available resources.

Deliverables

Abstract:	pdf
Proposal:	pdf
Report:	pdf
Presentation:	pdf
Project Code:	zip

Resources

XSEDE (formerly TeraGrid)

"A Computational Introduction to Number Theory and Algebra", by Victor Shoup

Acknowledgments

This research was supported in part by the Research Computing group at the Rochester Institute of Technology; and by the National Science Foundation through TeraGrid resources provided by Purdue University.

References

L. Adleman, A subexponential algorithm for the discrete logarithm problem with applications to cryptography, In Foundations of Computer Science, 1979., 20th Annual Symposium on.
Odlyzko, Andrew. Discrete Logarithms: The Past and the Future. Springer Netherlands, 2000.
D. R. Stinson. Cryptography Theory And Practice, 3rd edition. Chapman & Hall/CRC, 2006.
Shoup, Victor. A Computational Introduction to Number Theory and Algebra. Electronic Edition, version 2, 2008.