Leiden University Student Repository

Buuren, S. van (4480)

Spectra of Supersingular Isogeny Graphs

Master thesis | Mathematics (MSc)

In a 2007 paper, Charles, Lauter and Goren studied how one might use Ramanujan graphs to create cryptographic hash functions. One of the most well-known such graphs is the isogeny graph, whose vertices are indexed by the isomorphism classes of supersingular elliptic curves in a characteristic p. In this thesis, we study the spectra of these graphs. To start, we give two algorithms to compute these graphs for small p, and present data obtained from implementing these algorithms. This data provides some statistical evidence for several properties of the spectra of these graphs. We discuss the proof of two of these properties. Firstly, the fact that these supersingular isogeny graphs are Ramanujan, i.e. that they have large spectral gap. For this, we discuss the relation with Hecke operators and the Eichler–Shimura relation. Secondly, the distribution of the eigenvalues as p tends to infinity. This we prove via the relation between the graph and the Brandt matrices for the quaternion...Show moreIn a 2007 paper, Charles, Lauter and Goren studied how one might use Ramanujan graphs to create cryptographic hash functions. One of the most well-known such graphs is the isogeny graph, whose vertices are indexed by the isomorphism classes of supersingular elliptic curves in a characteristic p. In this thesis, we study the spectra of these graphs. To start, we give two algorithms to compute these graphs for small p, and present data obtained from implementing these algorithms. This data provides some statistical evidence for several properties of the spectra of these graphs. We discuss the proof of two of these properties. Firstly, the fact that these supersingular isogeny graphs are Ramanujan, i.e. that they have large spectral gap. For this, we discuss the relation with Hecke operators and the Eichler–Shimura relation. Secondly, the distribution of the eigenvalues as p tends to infinity. This we prove via the relation between the graph and the Brandt matrices for the quaternion algebra ramified at p and ?. We sketch a proof of the Eichler–Selberg trace formula, and use this to conclude the proof.Show less

Author

Buuren, S. van

Faculty

Faculty of Science

Supervisors

Vonk, J.B.

ECTS Credits

40

Language

en