bridge/class-master/depend/pari/src/basemath/ellsea.c
/* E is an elliptic curve defined over Z or over Fp in ellinit format, defined
 * by the equation E: y^2 + a1*x*y + a2*y = x^3 + a2*x^2 + a4*x + a6
 * p is a prime number
 * set smallfact to stop whenever a small factor of the order, not dividing smallfact,
 * is detected. Useful when searching for a good curve for cryptographic
 * applications */
E is an elliptic curve defined over Z or over Fp in ellinit format, defined
by the equation E: y^2 + a1*x*y + a2*y = x^3 + a2*x^2 + a4*x + a6
p is a prime number
set smallfact to stop whenever a small factor of the order, not dividing smallfact,
is detected. Useful when searching for a good curve for cryptographic
applications
E is an elliptic curve defined over Z or over Fp in ellinit format defined by the equation E : y^2 + a1 * x * y + a2 * y = x^3 + a2 * x^2 + a4 * x + a6 p is a prime number set smallfact to stop whenever a small factor of the order not dividing smallfact is detected . Useful when searching for a good curve for cryptographic applications
GEN
Fq_ellcard_SEA(GEN a4, GEN a6, GEN q, GEN T, GEN p, long smallfact)
{
  const long MAX_ATKIN = 21;
  pari_sp ltop = avma, btop;
  long ell, i, nb_atkin, vx,vy;
  GEN TR, TR_mod, compile_atkin, bound, bound_bsgs, champ;
  GEN prod_atkin = gen_1, max_traces = gen_0;
  GEN j;
  double bound_gr = 1.;
  const double growth_factor = 1.26;
  forprime_t TT;
  j = Fq_ellj(a4, a6, T, p);
  if (signe(j) == 0 || signe(Fq_sub(j, utoi(1728), T, p)) == 0)
    return T ? FpXQ_ellcard(Fq_to_FpXQ(a4, T, p), Fq_to_FpXQ(a6, T, p), T, p)
             : Fp_ellcard(a4, a6, p);
  switch(FqX_nbroots(rhs(a4, a6, 0), T, p))
  {
  case 3: 
    i = mod4(q)+1; if (i > 2) i -= 4;
    TR_mod = utoipos(4);
    TR = stoi(i); break;
  case 1:
    TR_mod = gen_2;
    TR = gen_0; break;
  default : 
    TR_mod = gen_2;
    TR = gen_1; break;
  }
  if (odd(smallfact) && !mpodd(TR))
  {
    if (DEBUGLEVEL) err_printf("Aborting: #E(Fq) divisible by 2\n");
    avma = ltop; return gen_0;
  }
  vy = fetch_var();
  vx = fetch_var_higher();
  u_forprime_init(&TT, 3, ULONG_MAX);
  bound = sqrti(shifti(q, 4));
  bound_bsgs = get_bound_bsgs(expi(q));
  compile_atkin = zerovec(MAX_ATKIN); nb_atkin = 0;
  btop = avma;
  while ( (ell = u_forprime_next(&TT)) )
  {
    long ellkt, kt = 1, nbtrace;
    GEN trace_mod;
    if (absequalui(ell, p)) continue;
    trace_mod = find_trace(a4, a6, j, ell, q, T, p, &kt, smallfact, vx,vy);
    if (!trace_mod) continue;
    nbtrace = lg(trace_mod) - 1;
    ellkt = (long)upowuu(ell, kt);
    if (nbtrace == 1)
    {
      long t_mod_ellkt = trace_mod[1];
      if (smallfact && smallfact%ell!=0)
      { 
        long q_mod_ell_plus_one = umodiu(q,ell) + 1;
        ulong  card_mod_ell = umodsu(q_mod_ell_plus_one - t_mod_ellkt, ell);
        ulong tcard_mod_ell = 1;
        if (card_mod_ell && smallfact < 0)
          tcard_mod_ell = umodsu(q_mod_ell_plus_one + t_mod_ellkt, ell);
        if (!card_mod_ell || !tcard_mod_ell)
        {
          if (DEBUGLEVEL)
            err_printf("\nAborting: #E%s(Fq) divisible by %ld\n",
                       tcard_mod_ell ? "" : "_twist", ell);
          delete_var();
          delete_var();
          avma = ltop; return gen_0;
        }
      }
      (void)Z_incremental_CRT(&TR, t_mod_ellkt, &TR_mod, ellkt);
      if (DEBUGLEVEL)
        err_printf(", missing %ld bits\n",expi(bound)-expi(TR_mod));
    }
    else
    {
      add_atkin(compile_atkin, mkvec2(utoipos(ellkt), trace_mod), &nb_atkin);
      prod_atkin = value(-1, compile_atkin, nb_atkin);
    }
    if (cmpii(mulii(TR_mod, prod_atkin), bound) > 0)
    {
      GEN bound_tr;
      if (!nb_atkin)
      {
        delete_var();
        delete_var();
        return gerepileuptoint(ltop, subii(addiu(q, 1), TR));
      }
      bound_tr = mulrr(bound_bsgs, dbltor(bound_gr));
      bound_gr *= growth_factor;
      if (signe(max_traces))
      {
        max_traces = divis(muliu(max_traces,nbtrace), ellkt);
        if (DEBUGLEVEL>=3)
          err_printf("At least %Ps remaining possibilities.\n",max_traces);
      }
      if (cmpir(max_traces, bound_tr) < 0)
      {
        GEN bound_atkin = truedivii(bound, TR_mod);
        champ = champion(compile_atkin, nb_atkin, bound_atkin);
        max_traces = gel(champ,2);
        if (DEBUGLEVEL>=2)
          err_printf("%Ps remaining possibilities.\n", max_traces);
        if (cmpir(max_traces, bound_tr) < 0)
        {
          GEN res, cat = shallowextract(compile_atkin, gel(champ,1));
          const struct bb_group *grp;
          void *E;
          if (DEBUGLEVEL)
            err_printf("Match and sort for %Ps possibilities.\n", max_traces);
          delete_var();
          delete_var();
          grp = get_FqE_group(&E,a4,a6,T,p);
          res = match_and_sort(cat, TR_mod, TR, q, E, grp);
          return gerepileuptoint(ltop, res);
        }
      }
    }
    if (gc_needed(btop, 1))
      gerepileall(btop,5, &TR,&TR_mod, &compile_atkin, &max_traces, &prod_atkin);
  }
  return NULL;
}
GEN Fq_ellcard_SEA ( GEN a4 , GEN a6 , GEN q , GEN T , GEN p , long smallfact ) { const long MAX_ATKIN = 21 ; pari_sp ltop = avma , btop ; long ell , i , nb_atkin , vx , vy ; GEN TR , TR_mod , compile_atkin , bound , bound_bsgs , champ ; GEN prod_atkin = gen_1 , max_traces = gen_0 ; GEN j ; double bound_gr = 1. ; const double growth_factor = 1.26 ; forprime_t TT ; j = Fq_ellj ( a4 , a6 , T , p ) ; if ( signe ( j ) == 0 || signe ( Fq_sub ( j , utoi ( 1728 ) , T , p ) ) == 0 ) return T ? FpXQ_ellcard ( Fq_to_FpXQ ( a4 , T , p ) , Fq_to_FpXQ ( a6 , T , p ) , T , p ) : Fp_ellcard ( a4 , a6 , p ) ; switch ( FqX_nbroots ( rhs ( a4 , a6 , 0 ) , T , p ) ) { case 3 : i = mod4 ( q ) + 1 ; if ( i > 2 ) i -= 4 ; TR_mod = utoipos ( 4 ) ; TR = stoi ( i ) ; break ; case 1 : TR_mod = gen_2 ; TR = gen_0 ; break ; default : TR_mod = gen_2 ; TR = gen_1 ; break ; } if ( odd ( smallfact ) && ! mpodd ( TR ) ) { if ( DEBUGLEVEL ) err_printf ( " \n " ) ; avma = ltop ; return gen_0 ; } vy = fetch_var ( ) ; vx = fetch_var_higher ( ) ; u_forprime_init ( & TT , 3 , ULONG_MAX ) ; bound = sqrti ( shifti ( q , 4 ) ) ; bound_bsgs = get_bound_bsgs ( expi ( q ) ) ; compile_atkin = zerovec ( MAX_ATKIN ) ; nb_atkin = 0 ; btop = avma ; while ( ( ell = u_forprime_next ( & TT ) ) ) { long ellkt , kt = 1 , nbtrace ; GEN trace_mod ; if ( absequalui ( ell , p ) ) continue ; trace_mod = find_trace ( a4 , a6 , j , ell , q , T , p , & kt , smallfact , vx , vy ) ; if ( ! trace_mod ) continue ; nbtrace = lg ( trace_mod ) - 1 ; ellkt = ( long ) upowuu ( ell , kt ) ; if ( nbtrace == 1 ) { long t_mod_ellkt = trace_mod [ 1 ] ; if ( smallfact && smallfact % ell != 0 ) { long q_mod_ell_plus_one = umodiu ( q , ell ) + 1 ; ulong card_mod_ell = umodsu ( q_mod_ell_plus_one - t_mod_ellkt , ell ) ; ulong tcard_mod_ell = 1 ; if ( card_mod_ell && smallfact < 0 ) tcard_mod_ell = umodsu ( q_mod_ell_plus_one + t_mod_ellkt , ell ) ; if ( ! card_mod_ell || ! tcard_mod_ell ) { if ( DEBUGLEVEL ) err_printf ( " \n \n " , tcard_mod_ell ? " " : " " , ell ) ; delete_var ( ) ; delete_var ( ) ; avma = ltop ; return gen_0 ; } } ( void ) Z_incremental_CRT ( & TR , t_mod_ellkt , & TR_mod , ellkt ) ; if ( DEBUGLEVEL ) err_printf ( " \n " , expi ( bound ) - expi ( TR_mod ) ) ; } else { add_atkin ( compile_atkin , mkvec2 ( utoipos ( ellkt ) , trace_mod ) , & nb_atkin ) ; prod_atkin = value ( -1 , compile_atkin , nb_atkin ) ; } if ( cmpii ( mulii ( TR_mod , prod_atkin ) , bound ) > 0 ) { GEN bound_tr ; if ( ! nb_atkin ) { delete_var ( ) ; delete_var ( ) ; return gerepileuptoint ( ltop , subii ( addiu ( q , 1 ) , TR ) ) ; } bound_tr = mulrr ( bound_bsgs , dbltor ( bound_gr ) ) ; bound_gr *= growth_factor ; if ( signe ( max_traces ) ) { max_traces = divis ( muliu ( max_traces , nbtrace ) , ellkt ) ; if ( DEBUGLEVEL >= 3 ) err_printf ( " \n " , max_traces ) ; } if ( cmpir ( max_traces , bound_tr ) < 0 ) { GEN bound_atkin = truedivii ( bound , TR_mod ) ; champ = champion ( compile_atkin , nb_atkin , bound_atkin ) ; max_traces = gel ( champ , 2 ) ; if ( DEBUGLEVEL >= 2 ) err_printf ( " \n " , max_traces ) ; if ( cmpir ( max_traces , bound_tr ) < 0 ) { GEN res , cat = shallowextract ( compile_atkin , gel ( champ , 1 ) ) ; const struct bb_group * grp ; void * E ; if ( DEBUGLEVEL ) err_printf ( " \n " , max_traces ) ; delete_var ( ) ; delete_var ( ) ; grp = get_FqE_group ( & E , a4 , a6 , T , p ) ; res = match_and_sort ( cat , TR_mod , TR , q , E , grp ) ; return gerepileuptoint ( ltop , res ) ; } } } if ( gc_needed ( btop , 1 ) ) gerepileall ( btop , 5 , & TR , & TR_mod , & compile_atkin , & max_traces , & prod_atkin ) ; } return NULL ; }
E is an elliptic curve defined over Z or over Fp in ellinit format, defined
 by the equation E: y^2 + a1*x*y + a2*y = x^3 + a2*x^2 + a4*x + a6
 p is a prime number
 set smallfact to stop whenever a small factor of the order, not dividing smallfact,
 is detected.
E is an elliptic curve defined over Z or over Fp in ellinit format defined by the equation E : y^2 + a1 * x * y + a2 * y = x^3 + a2 * x^2 + a4 * x + a6 p is a prime number set smallfact to stop whenever a small factor of the order not dividing smallfact is detected .
/*First compute the trace modulo 2 */ /* bonus time: 4 | #E(Fq) = q+1 - t */ /* 0 */ /* compile_atkin is a vector containing informations about Atkin primes,
   * informations about Elkies primes lie in Mod(TR, TR_mod). */ /* does ell divide q + 1 - t ? */ /*LCOV_EXCL_LINE*/