Re: CONSTRUCTING ELLIPTIC CURVES OF PRESCRIBED ORDER

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Thu, May 28, 2020 at 01:41:04PM +0200, Michael Hortmann wrote:
> https://openaccess.leidenuniv.nl/bitstream/handle/1887/4425/Thesis.pdf
> https://www.win.tue.nl/diamant/symposium05/abstracts/broeker.pdf
> https://link.springer.com/chapter/10.1007/978-3-540-24847-7_8
> 
> No CM.

At least this algorithm 
https://www.win.tue.nl/diamant/symposium05/abstracts/broeker.pdf
use CM heavily.

However this is very easy to implement in GP:

findDP(N)=
{
  my(F=[4*N,factor(4*N)]);
  for(d=5,oo,my(D=-d);
    V=qfbsolve(Qfb(1,0,-D),F,1);
    if(V,
      for(i=1,#V,
        my(p=N+1-V[i][1]);
        if(ispseudoprime(p),return([D,p])))));
}

findE(N)=
{
  my([D,p]=findDP(N));
  my(j=polrootsmod(polclass(D),p)[1]);
  my(E=ellinit(ellfromj(j)));
  if(ellcard(E)!=N,E=ellinit(elltwist(E)));
  E;
}

? findDP(10^1000+453)
%4 =
[-2643,10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000084580564865659365122376528413332645532152171127546438119158218509746454894047502311475921435925593395788663825537350510530446716403741222340985964099742528845624992705649011211562977747791787795828408878166796544029225171287772986659453369047576935911760465854704590139939913782088978690725584432808323194356221767413951670691765171583388575651408252249668909097564489522144887781732134899389587753697361876577100306912030685148084979302637035928995834607369105121944422262464187611018973884015439291]

? E = findE(10^100+267);
? ellcard(E)
%14 =
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000267

(for large N, you do not want to use ellcard, there are faster way to
pick between E and its twist)

Cheers,
Bill.