---
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 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.'
author:
- 'David Kohel, Kristin Lauter, Christophe Petit[^1], Jean-Pierre Tignol'
title: 'On the quaternion $\ell$-isogeny path problem'
---

*To appear in the LMS Journal of Computation and Mathematics, as a special issue for ANTS (Algorithmic Number Theory Symposium) conference.*

Introduction {#sec:introduction}
============

In this paper, we provide a probabilistic algorithm to solve a quaternion ideal analog of the path problem in supersingular $\ell$-isogeny graphs. The main result is an algorithm for the following. Let ${B_{p,\infty}}$ be a quaternion algebra over ${\mathbb{Q}}$ ramified at $p$ and $\infty$. Let $\ell$ be a “small” prime, typically 2 or 3, or any small constant prime. Given a maximal quaternion 