|
Friday, November 28, 2008 |
|
|
|
|
Constructing expander graphs from the Generalized Riemann Hypothesis |
|
|
We present a construction of expander graphs obtained from Cayley graphs
of narrow ray class groups, whose eigenvalue bounds follow from the
Generalized Riemann Hypothesis. Our result implies that the Cayley
graph of $(\mathbf{Z}/q\mathbf{Z})^*$ with respect to small prime
generators is an expander. As another application, we explain the
relationship between the expansion properties of these graphs and the
security of the elliptic curve discrete logarithm problem. |