  Let $\cO$ 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 $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 breaks 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.

Number Theory