Expander graphs based on GRH with an application to elliptic curve cryptography
| Autor: | Stephen D. Miller, David Jao, Ramarathnam Venkatesan |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
Discrete mathematics
Algebra and Number Theory Mathematics - Number Theory Cayley graph 010102 general mathematics Hessian form of an elliptic curve 0102 computer and information sciences 01 natural sciences Supersingular elliptic curve Combinatorics Vertex-transitive graph 010201 computation theory & mathematics Jacobian curve ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION FOS: Mathematics Counting points on elliptic curves Mathematics - Combinatorics Expander graph Number Theory (math.NT) Combinatorics (math.CO) 0101 mathematics Schoof's algorithm MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Journal of Number Theory. 129:1491-1504 |
| ISSN: | 0022-314X |
| DOI: | 10.1016/j.jnt.2008.11.006 |
| Popis: | 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 (Z/qZ)* with respect to small prime generators is an expander. As another application, we show that the graph of small prime degree isogenies between ordinary elliptic curves achieves non-negligible eigenvalue separation, and explain the relationship between the expansion properties of these graphs and the security of the elliptic curve discrete logarithm problem. Comment: 24 pages, to appear in the Journal of Number Theory |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect