bridge/class-master/depend/pari/src/basemath/arith1.c
/* h(x) for x<0 using Baby Step/Giant Step.
 * Assumes G is not too far from being cyclic.
 *
 * Compute G^2 instead of G so as to kill most of the non-cyclicity */
h(x) for x<0 using Baby Step/Giant Step.
Assumes G is not too far from being cyclic.

Compute G^2 instead of G so as to kill most of the non-cyclicity
h ( x ) for x<0 using Baby Step / Giant Step . Assumes G is not too far from being cyclic . Compute G^2 instead of G so as to kill most of the non - cyclicity
GEN
classno(GEN x)
{
  pari_sp av = avma;
  long r2, k, s, i, l;
  GEN forms, hin, Hf, D, g1, d1, d2, q, L, fad1, order_bound;
  void *E;
  if (signe(x) >= 0) return classno2(x);
  check_quaddisc(x, &s, &k, "classno");
  if (abscmpiu(x,12) <= 0) return gen_1;
  Hf = conductor_part(x, k, &D, NULL);
  if (abscmpiu(D,12) <= 0) return gerepilecopy(av, Hf);
  forms =  get_forms(D, &L);
  r2 = two_rank(D);
  hin = roundr(shiftr(L, -r2)); 
  l = lg(forms);
  order_bound = const_vec(l-1, NULL);
  E = expi(D) > 60? (void*)sqrtnint(shifti(absi_shallow(D),-2),4): NULL;
  g1 = gel(forms,1);
  gel(order_bound,1) = d1 = Shanks_order(E, g1, hin, &fad1);
  q = diviiround(hin, d1); 
  d2 = NULL; 
  if (is_pm1(q)) goto END;
  for (i=2; i < l; i++)
  {
    GEN o, fao, a, F, fd, f = gel(forms,i);
    fd = powgi(f, d1); if (is_pm1(gel(fd,1))) continue;
    F = powgi(fd, q);
    a = gel(F,1);
    o = is_pm1(a)? find_order(E, fd, q, &fao): Shanks_order(E, fd, q, &fao);
    fao = merge_factor(fad1,fao, (void*)&cmpii, &cmp_nodata);
    o = find_order(E, f, fao, &fao);
    gel(order_bound,i) = o;
    update_g1(&g1,&d1,&fad1, f,o,fao);
    q = diviiround(hin, d1);
    if (is_pm1(q)) goto END;
  }
  if (expi(q) > 3)
  { 
    ulong N, n = 2*itou(sqrti(d1));
    GEN D = d1, T = gen_Shanks_init(g1, n, E, &qfi_group);
    d2 = gen_1;
    N = itou( gceil(gdivgs(d1,n)) ); 
    for (i = 1; i < l; i++)
    {
      GEN d, f = gel(forms,i), B = gel(order_bound,i);
      if (!B) B = find_order(E, f, fad1, &d);
      f = powgi(f,d2);
      if (equal1(E, T,N,f)) continue;
      B = gdiv(B,d2); if (typ(B) == t_FRAC) B = gel(B,1);
      d = relative_order(E, f, B, N,T);
      d2= mulii(d,d2);
      D = mulii(d1,d2);
      q = diviiround(hin,D);
      if (is_pm1(q)) { d1 = D; goto END; }
    }
    d1 = D; 
  }
  if (!ok_q(q,d1,d2,r2))
  {
    GEN q0 = q;
    long d;
    if (cmpii(mulii(q,d1), hin) < 0)
    { 
      d = 1;
      do { q = addis(q0,d); d = d>0? -d: 1-d; } while(!ok_q(q,d1,d2,r2));
    }
    else
    { 
      d = -1;
      do { q = addis(q0,d); d = d<0? -d: -1-d; } while(!ok_q(q,d1,d2,r2));
    }
  }
  d1 = mulii(d1,q);
END:
  return gerepileuptoint(av, shifti(mulii(d1,Hf), r2));
}
GEN classno ( GEN x ) { pari_sp av = avma ; long r2 , k , s , i , l ; GEN forms , hin , Hf , D , g1 , d1 , d2 , q , L , fad1 , order_bound ; void * E ; if ( signe ( x ) >= 0 ) return classno2 ( x ) ; check_quaddisc ( x , & s , & k , " " ) ; if ( abscmpiu ( x , 12 ) <= 0 ) return gen_1 ; Hf = conductor_part ( x , k , & D , NULL ) ; if ( abscmpiu ( D , 12 ) <= 0 ) return gerepilecopy ( av , Hf ) ; forms = get_forms ( D , & L ) ; r2 = two_rank ( D ) ; hin = roundr ( shiftr ( L , - r2 ) ) ; l = lg ( forms ) ; order_bound = const_vec ( l - 1 , NULL ) ; E = expi ( D ) > 60 ? ( void * ) sqrtnint ( shifti ( absi_shallow ( D ) , -2 ) , 4 ) : NULL ; g1 = gel ( forms , 1 ) ; gel ( order_bound , 1 ) = d1 = Shanks_order ( E , g1 , hin , & fad1 ) ; q = diviiround ( hin , d1 ) ; d2 = NULL ; if ( is_pm1 ( q ) ) goto END ; for ( i = 2 ; i < l ; i ++ ) { GEN o , fao , a , F , fd , f = gel ( forms , i ) ; fd = powgi ( f , d1 ) ; if ( is_pm1 ( gel ( fd , 1 ) ) ) continue ; F = powgi ( fd , q ) ; a = gel ( F , 1 ) ; o = is_pm1 ( a ) ? find_order ( E , fd , q , & fao ) : Shanks_order ( E , fd , q , & fao ) ; fao = merge_factor ( fad1 , fao , ( void * ) & cmpii , & cmp_nodata ) ; o = find_order ( E , f , fao , & fao ) ; gel ( order_bound , i ) = o ; update_g1 ( & g1 , & d1 , & fad1 , f , o , fao ) ; q = diviiround ( hin , d1 ) ; if ( is_pm1 ( q ) ) goto END ; } if ( expi ( q ) > 3 ) { ulong N , n = 2 * itou ( sqrti ( d1 ) ) ; GEN D = d1 , T = gen_Shanks_init ( g1 , n , E , & qfi_group ) ; d2 = gen_1 ; N = itou ( gceil ( gdivgs ( d1 , n ) ) ) ; for ( i = 1 ; i < l ; i ++ ) { GEN d , f = gel ( forms , i ) , B = gel ( order_bound , i ) ; if ( ! B ) B = find_order ( E , f , fad1 , & d ) ; f = powgi ( f , d2 ) ; if ( equal1 ( E , T , N , f ) ) continue ; B = gdiv ( B , d2 ) ; if ( typ ( B ) == t_FRAC ) B = gel ( B , 1 ) ; d = relative_order ( E , f , B , N , T ) ; d2 = mulii ( d , d2 ) ; D = mulii ( d1 , d2 ) ; q = diviiround ( hin , D ) ; if ( is_pm1 ( q ) ) { d1 = D ; goto END ; } } d1 = D ; } if ( ! ok_q ( q , d1 , d2 , r2 ) ) { GEN q0 = q ; long d ; if ( cmpii ( mulii ( q , d1 ) , hin ) < 0 ) { d = 1 ; do { q = addis ( q0 , d ) ; d = d > 0 ? - d : 1 - d ; } while ( ! ok_q ( q , d1 , d2 , r2 ) ) ; } else { d = -1 ; do { q = addis ( q0 , d ) ; d = d < 0 ? - d : -1 - d ; } while ( ! ok_q ( q , d1 , d2 , r2 ) ) ; } } d1 = mulii ( d1 , q ) ; END : return gerepileuptoint ( av , shifti ( mulii ( d1 , Hf ) , r2 ) ) ; }
h(x) for x<0 using Baby Step/Giant Step.
h ( x ) for x<0 using Baby Step / Giant Step .
/* rough approximation for #G, G = Cl(K)^2 */ /* approximate order of G/<g1> */ /* not computed yet */ /* f^(d1 q) = 1 */ /* o = order of f, fao = factor(o) */ /* very probably d1 = expo(Cl^2(K)), q ~ #Cl^2(K) / d1 */ /* q large: compute d2, 2nd elt divisor */ /* order(g1) <= n*N */ /*junk*/ /* f^B = 1 */ /* very probably, d2 is the 2nd elementary divisor */ /* product of first two elt divisors */ /* impose q | d2^oo (d1^oo if d2 not computed), and compatible with known
   * 2-rank */ /* try q = q0+1,-1,+2,-2 */ /* q0-1,+1,-2,+2  */