The correspondence between maximal orders in a quaternion algebra and supersingular elliptic curves has uncovered new perspectives in the field of isogeny-based cryptography. The KLPT algorithm of Kohel et al. in 2014 introduces an algorithm solving the quaternion isogeny path problem in polynomial time. Studying this problem has applications both constructive and destructive. It has allowed to reduce the problem of computing isogenies between two curves to the one of endomorphism ring computation. The GPS signature scheme from Galbraith et al. in 2017 was built on this algorithm.
The main algorithm of KLPT solves the problem when the maximal order is special extremal. The paper also proposes a generalized version, but it produces an output with some very characteristic property that prevent from using it in some applications, like a generalization of the GPS signature. In this work, we propose a new method to generalize the algorithm. It produces a shorter solution with the same time complexity and without the problematic property.