Document Type


Publication Date


First Advisor

Joshua Holden


Cryptography is being used today more than it ever has in the past. Millions of transactions are being conducted every hour using encrypted channels, most of which use the Internet as their medium. It is taken for granted by the average user that these transaction are secure, but mathematicians and computer scientists alike are constantly testing the algorithms being used. Several of these cryptosystems use the transformation

gx = y (mod n)

The appeal of this transformation is that it is quite simple to calculate gx mod n; exponentiation by squaring is fairly simple and quick even using very large numbers. However there is no known algorithm to compute the inverse of the transformation (that is given y, g, and n, (and x) in a comparable amount of time. This is called the discrete log problem, and Diffie-Hellman key exchange, RSA and the Blum-Micali pseudorandom bit generator all rely on its inherent difficulty. This paper explores the maps generated by this transformation with the hope of gaining some insight into its structure and similarity to random mappings.


MSTR 08-06

Included in

Number Theory Commons