search

sagemath / sage

Main repository of SageMath. Now open for Issues and Pull Requests.
https://www.sagemath.org
Other
1.2k stars 413 forks source link

Endomorphism rings of elliptic curves #31851

Open 11d1fc49-71a1-44e1-869f-76be013245a0 opened 3 years ago

11d1fc49-71a1-44e1-869f-76be013245a0 commented 3 years ago

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 commented 3 years ago
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.

11d1fc49-71a1-44e1-869f-76be013245a0 commented 3 years ago
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.