Linear Congruential Generators Over Elliptic Curves
Sean Hallgren · 2001
Random numbers are useful in many applications such as Monte Carlo simulation, randomized algorithms, games, and password generation. It is important to be able to prove facts about about pseudo-random number generators, both about the distribution and the predictability of the pseudorandom numbers. I discuss a pseudo-random number generator based on elliptic curves taken over finite fields. This class of generators can produce provably good pseudo-random numbers. Also, I prove that the analog of a faster pseudo-random number generator embedded in an elliptic curve fails to produce good pseudo-random numbers. This report was submitted in partial fulfillment of the requirements for the Senior Honors Research Program in the School of Computer Science at Carnegie Mellon University. Keywords: cryptography, pseudo-random number generation, elliptic curves, linear congruential generators 1 Introduction Random numbers are useful in many applications such as Monte Carlo simulation, random...