Re: CONSTRUCTING ELLIPTIC CURVES OF PRESCRIBED ORDER

[Andreas Enge <andreas.enge@inria.fr>]

On Thu, May 28, 2020 at 01:15:57PM +0200, Bill Allombert wrote:
> On Thu, May 28, 2020 at 09:21:02AM +0200, Michael Hortmann wrote:
> > There is an algorithm by Bröker/Stevenhagen for constructing elliptic
> > curves of prescribed order. Has anybody seen an implementation for Pari/gp?
> > (Or another computer algebra system)?
> Could you give a reference to the algorithm ?
> Is it based on complex-multiplication theory ?

Yes, it is based on CM. The algorithm requires a factorisation of the
number of points, and then solves the (system of) CM equations:
N = p+1 +- t (with |t| roughly bounded by 2*sqrt(N))
4p = t^2 - v^2 D, where D<0 is the CM discriminant,
     |D| is small and thus v large

This first step is the "converse" of CM for finding cryptographic curves:
Instead of fixing p and finding N (with the property of being prime) and
a small D, one fixes N and finds p prime and a small D.

Once p and D are found, the CM step of computing a class polynomial and
deducing an elliptic curve modulo p with N points is the same; it can
easily (depending on the size of D...) be done in PARI/GP.

Andreas