Connecting Kani's Lemma and path-finding in the Bruhat-Tits tree to compute supersingular endomorphism rings
<|reference_start|>Connecting Kani's Lemma and path-finding in the Bruhat-Tits tree to compute supersingular endomorphism rings: We give a deterministic polynomial time algorithm to compute the endomorphism ring of a supersingular elliptic curve in characteristic p, provided that we are given two noncommuting endomorphisms and the factorization of the discriminant of the ring $\mathcal{O}_0$ they generate. At each prime $q$ for which $\mathcal{O}_0$ is not maximal, we compute the endomorphism ring locally by computing a q-maximal order containing it and, when $q \neq p$, recovering a path to $\text{End}(E) \otimes \mathbb{Z}_q$ in the Bruhat-Tits tree. We use techniques of higher-dimensional isogenies to navigate towards the local endomorphism ring. Our algorithm improves on a previous algorithm which requires a restricted input and runs in subexponential time under certain heuristics. Page and Wesolowski give a probabilistic polynomial time algorithm to compute the endomorphism ring on input of a single non-scalar endomorphism. Beyond using techniques of higher-dimensional isogenies to divide endomorphisms by a scalar, our methods are completely different.<|reference_end|>
@article{eisentraeger2024connecting,
    title={Connecting Kani's Lemma and path-finding in the Bruhat-Tits tree to
  compute supersingular endomorphism rings},
    author={Kirsten Eisentraeger and Gabrielle Scullard},
    journal={arXiv preprint arXiv:2402.05059},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.05059},
    primaryClass={math.NT cs.CR}
}