Endomorphism rings of elliptic curves

[loefflerd]

Given an ordinary elliptic curve over a finite field, its endomorphism ring is an order in an imaginary quadratic field, which contains the order generated by the Frobenius (as computed by frobenius_order) but is in general larger. It would be nice to have an algorithm -- even a simple "toy" one -- to compute the endomorphism ring. This question came up on math.stackexchange, and there is working code linked from the answer:

https://math.stackexchange.com/questions/4147940/computing-the-endomorphism-ring-of-an-elliptic-curve-over-a-finite-field-in-sag

(Even better, I guess, would be computing an explicit isogeny of smallish degree which generates the endomorphism ring.)

CC: @defeo @yyyyx4

Component: elliptic curves

Keywords: endomorphisms, finite fields

Issue created by migration from https://trac.sagemath.org/ticket/31851

[defeo]

comment:1

I believe some variant of Kohel's algorithm should be fairly easy to implement, and possibly more efficient than the code in the Stackexchange answer. The bottlneck in most cases would be the factorization of the discriminant. Then you just iterate over the prime factors ℓ of Δ that have valuation >1, and either compute ℓ-isogenies or compute the action of Frobenius on E[ℓ].

Of course, if ℓ is too large you have a problem, but then the only way around is the Bisson-Sutherland algorithm.

[loefflerd]

comment:2

It would be great to have an implementation of the fancier algorithms of Kohel or of Bisson-Sutherland. However, a simplistic and slow implementation is (IMHO) considerably better than having no implementation at all, as at present.

[yyyyx4]

See #38493 for a patch to compute the endomorphism ring abstractly (as a quadratic order). Finding the generating endomorphism as an explicit isogeny is work in progress.