Document Type


Publication Date


First Advisor

Joshua Holden


The discrete logarithm problem, and its adaptation to elliptic curves, called the elliptic curve discrete logarithm problem (ECDLP) is an open problem in the field of number theory, and its applications to modern cryptographic algorithms are numerous. This paper focuses on a statistical analysis of a modification to the ECDLP, called the x-ECDLP, where one is only given the xcoordinate of a point, instead of the entire point. Focusing only on elliptic curves whose field of definition is smaller than the number of points, this paper attempts to find a statistical indication of underlying structure (or lack thereof) in the ECDLP. Using functional graphs, this translates into discovering certain structure in the functional graphs induced by the ECDLP on a wide range of elliptic curves, and comparing these statistics to what would be expected of a random functional graph. A lack of randomness may translate into an exploitable structure in the ECDLP that would undermine the security of cryptographic algorithms based on this problem. In addition to providing an extensive list of data for small primes, this paper details a generating function for the number of elliptic curve functional graphs (ECFGs).


MSTR 11-01

Included in

Number Theory Commons