LMS Journal of Computation and Mathematics · 2014 · 124 citations · 6 references
ComputingComputer ScienceMathematicsAlgebraAlgorithmsTheory Of ComputationAlgebraic Number TheoryArithmetic GeometryElliptic Curve CryptographyElliptic CurvesHash FunctionsNumber-theoretic AlgorithmsAlgebraic CryptanalysisElliptic Curve ArithmeticElliptic Curves In GeometryIsogeny ComputationPolynomial Time ComplexityPolynomial-time AlgorithmsQuaternion RepresentationSupersingular Elliptic Curves
Abstract Let $\mathcal{O}$ be a maximal order in a definite quaternion algebra over $\mathbb{Q}$ of prime discriminant $p$ , and $\ell $ a small prime. We describe a probabilistic algorithm which, for a given left $\mathcal{O}$ -ideal, computes a representative in its left ideal class of $\ell $ -power norm. In practice the algorithm is efficient and, subject to heuristics on expected distributions of primes, runs in expected polynomial time. This solves the underlying problem for a quaternion analog of the Charles–Goren–Lauter hash function, and has security implications for the original CGL construction in terms of supersingular elliptic curves.
6
John Cannon, Wieb Bosma, Claus Fieker et al. · 2011 · 600 citations
Cryptographic Hash Functions from Expander Graphs
Denis Charles, Kristin Lauter, Eyal Z. Goren · Journal of Cryptology · 2007 · 366 citations · Full text
Explicit bounds for primality testing and related problems
Eric Bach · Mathematics of Computation · 1990 · 212 citations · Full text
The Least Quadratic Non Residue
N. C. Ankeny · Annals of Mathematics · 1952 · 209 citations
Helmut Maier · The Michigan Mathematical Journal · 1985 · 152 citations · Full text