bridge/class-master/depend/pari/src/basemath/elltors.c
/* Bound for the elementary divisors of the torsion group of elliptic curve
 * Reduce the curve modulo some small good primes */
Bound for the elementary divisors of the torsion group of elliptic curve
Reduce the curve modulo some small good primes
Bound for the elementary divisors of the torsion group of elliptic curve Reduce the curve modulo some small good primes
static GEN
nftorsbound(GEN E)
{
  pari_sp av;
  long k = 0, g;
  GEN B1 = gen_0, B2 = gen_0, K = ellnf_get_nf(E);
  GEN D = ell_get_disc(E), ND = idealnorm(K,D);
  forprime_t S;
  if (typ(ND) == t_FRAC) ND = gel(ND,1);
  ND = mulii(ND, Q_denom(vecslice(E,1,5)));
  g = maxss(5, expi(ND) >> 3);
  if (g > 20) g = 20;
  (void)u_forprime_init(&S, 3, ULONG_MAX);
  av = avma;
  while (k < g) 
  {
    ulong p = u_forprime_next(&S);
    GEN P, gp;
    long j, l;
    if (!umodiu(ND,p)) continue;
    gp = utoipos(p);
    if (typ(D) != t_POLMOD) 
    {
      P = primedec_deg1(K, gp); 
      if (!P) continue;
      P = mkvec(P);
    }
    else
      P = idealprimedec_limit_f(K, utoipos(p), 1);
    l = lg(P);
    for (j = 1; j < l; j++,k++)
    {
      GEN Q = gel(P,j), EQ, cyc;
      long n;
      if ((ulong)pr_get_e(Q) >= p-1) continue;
      EQ = ellinit(E,zkmodprinit(K,Q),0);
      cyc = ellgroup(EQ, NULL);
      n = lg(cyc)-1;
      if (n == 0) return mkvec2(gen_1,gen_1);
      B1 = gcdii(B1,gel(cyc,1));
      B2 = (n == 1)? gen_1: gcdii(B2,gel(cyc,2));
      obj_free(EQ);
      if (Z_ispow2(B1)) return mkvec2(B1,B2);
    }
    if ((g & 15) == 0) gerepileall(av, 2, &B1, &B2);
  }
  if (abscmpiu(B2, 2) > 0)
  { 
    GEN n = gel(rootsof1(K), 1);
    B2 = gcdii(B2,n);
  }
  return mkvec2(B1,B2);
}
static GEN nftorsbound ( GEN E ) { pari_sp av ; long k = 0 , g ; GEN B1 = gen_0 , B2 = gen_0 , K = ellnf_get_nf ( E ) ; GEN D = ell_get_disc ( E ) , ND = idealnorm ( K , D ) ; forprime_t S ; if ( typ ( ND ) == t_FRAC ) ND = gel ( ND , 1 ) ; ND = mulii ( ND , Q_denom ( vecslice ( E , 1 , 5 ) ) ) ; g = maxss ( 5 , expi ( ND ) >> 3 ) ; if ( g > 20 ) g = 20 ; ( void ) u_forprime_init ( & S , 3 , ULONG_MAX ) ; av = avma ; while ( k < g ) { ulong p = u_forprime_next ( & S ) ; GEN P , gp ; long j , l ; if ( ! umodiu ( ND , p ) ) continue ; gp = utoipos ( p ) ; if ( typ ( D ) != t_POLMOD ) { P = primedec_deg1 ( K , gp ) ; if ( ! P ) continue ; P = mkvec ( P ) ; } else P = idealprimedec_limit_f ( K , utoipos ( p ) , 1 ) ; l = lg ( P ) ; for ( j = 1 ; j < l ; j ++ , k ++ ) { GEN Q = gel ( P , j ) , EQ , cyc ; long n ; if ( ( ulong ) pr_get_e ( Q ) >= p - 1 ) continue ; EQ = ellinit ( E , zkmodprinit ( K , Q ) , 0 ) ; cyc = ellgroup ( EQ , NULL ) ; n = lg ( cyc ) - 1 ; if ( n == 0 ) return mkvec2 ( gen_1 , gen_1 ) ; B1 = gcdii ( B1 , gel ( cyc , 1 ) ) ; B2 = ( n == 1 ) ? gen_1 : gcdii ( B2 , gel ( cyc , 2 ) ) ; obj_free ( EQ ) ; if ( Z_ispow2 ( B1 ) ) return mkvec2 ( B1 , B2 ) ; } if ( ( g & 15 ) == 0 ) gerepileall ( av , 2 , & B1 , & B2 ) ; } if ( abscmpiu ( B2 , 2 ) > 0 ) { GEN n = gel ( rootsof1 ( K ) , 1 ) ; B2 = gcdii ( B2 , n ) ; } return mkvec2 ( B1 , B2 ) ; }
Bound for the elementary divisors of the torsion group of elliptic curve
 Reduce the curve modulo some small good primes
Bound for the elementary divisors of the torsion group of elliptic curve Reduce the curve modulo some small good primes
/* P | p such that e(P/p) < p-1 => E(K) injects in E(k(P)) [otherwise
   * we may lose some p-torsion]*/ /* k = number of good primes already used */ /* primes of degree 1 are easier and give smaller bounds */ /* E/Q */ /* single P|p has all the information */ /* division by 2 is cheap when it fails, no need to have a sharp bound */ /* if E(K) has full n-torsion then K contains the n-th roots of 1 */