bridge/class-master/depend/pari/src/basemath/nffactor.c
/* Number of roots of unity in number field [nf]. */
Number of roots of unity in number field [nf].
Number of roots of unity in number field [ nf ] .
GEN
rootsof1(GEN nf)
{
  nflift_t L;
  GEN T, q, fa, LP, LE, C0, z, disc;
  pari_timer ti;
  long i, l, nbguessed, nbroots, nfdegree;
  pari_sp av;
  nf = checknf(nf);
  if (nf_get_r1(nf)) return trivroots();
  if (DEBUGLEVEL>2) timer_start(&ti);
  nbguessed = guess_roots(nf);
  if (DEBUGLEVEL>2)
    timer_printf(&ti, "guessing roots of 1 [guess = %ld]", nbguessed);
  if (nbguessed == 2) return trivroots();
  nfdegree = nf_get_degree(nf);
  fa = factoru(nbguessed);
  LP = gel(fa,1); l = lg(LP);
  LE = gel(fa,2);
  disc = nf_get_disc(nf);
  for (i = 1; i < l; i++)
  {
    long p = LP[i];
    if (p == 2)
    { 
      long v, vnf, k;
      if (LE[i] == 1) continue;
      vnf = vals(nfdegree);
      v = vali(disc);
      for (k = minss(LE[i], vnf+1); k >= 1; k--)
        if (v >= nfdegree*(k-1)) { nbguessed >>= LE[i]-k; LE[i] = k; break; }
    }
    else
    {
      long v, vnf, k;
      ulong r, q = udivuu_rem(nfdegree, p-1, &r);
      if (r) { nbguessed /= upowuu(p, LE[i]); LE[i] = 0; continue; }
      vnf = u_lval(q, p);
      v = Z_lval(disc, p);
      for (k = minss(LE[i], vnf+1); k >= 0; k--)
        if (v >= nfdegree*k-(long)q)
        { nbguessed /= upowuu(p, LE[i]-k); LE[i] = k; break; }
    }
  }
  if (DEBUGLEVEL>2)
    timer_printf(&ti, "after ramification conditions [guess = %ld]", nbguessed);
  if (nbguessed == 2) return trivroots();
  av = avma;
  T = nf_get_pol(nf);
  if (eulerphiu_fact(fa) == (ulong)nfdegree)
  {
    z = ZXirred_is_cyclo_translate(T, uissquarefree_fact(fa));
    if (DEBUGLEVEL>2) timer_printf(&ti, "checking for cyclotomic polynomial");
    if (z)
    {
      z = nf_to_scalar_or_basis(nf,z);
      return gerepilecopy(av, mkvec2(utoipos(nbguessed), z));
    }
    avma = av;
  }
  nf_pick_prime_for_units(nf, &L);
  if (DEBUGLEVEL>2)
    timer_printf(&ti, "choosing prime %Ps, degree %ld",
             L.p, L.Tp? degpol(L.Tp): 1);
  C0 = gmulsg(nfdegree, L2_bound(nf, gen_1));
  if (DEBUGLEVEL>2) err_printf("Lift pr^k; GSmin wanted: %Ps\n",C0);
  bestlift_init((long)mybestlift_bound(C0), nf, C0, &L);
  L.dn = NULL;
  if (DEBUGLEVEL>2) timer_start(&ti);
  nbroots = 2; z = gen_m1;
  q = powiu(L.p,degpol(L.Tp));
  for (i = 1; i < l; i++)
  { 
    long k, p = LP[i];
    for (k = minss(LE[i], Z_lval(subiu(q,1UL),p)); k > 0; k--)
    { 
      pari_sp av = avma;
      long pk = upowuu(p,k);
      GEN r;
      if (pk==2) continue; 
      r = nfcyclo_root(pk, T, &L);
      if (DEBUGLEVEL>2) timer_printf(&ti, "for factoring Phi_%ld^%ld", p,k);
      if (r) {
        if (DEBUGLEVEL>2) err_printf("  %s root of unity found\n",uordinal(pk));
        if (p==2) { nbroots = pk; z = r; }
        else     { nbroots *= pk; z = nfmul(nf, z,r); }
        break;
      }
      avma = av;
      if (DEBUGLEVEL) pari_warn(warner,"rootsof1: wrong guess");
    }
  }
  return gerepilecopy(av, mkvec2(utoi(nbroots), z));
}
GEN rootsof1 ( GEN nf ) { nflift_t L ; GEN T , q , fa , LP , LE , C0 , z , disc ; pari_timer ti ; long i , l , nbguessed , nbroots , nfdegree ; pari_sp av ; nf = checknf ( nf ) ; if ( nf_get_r1 ( nf ) ) return trivroots ( ) ; if ( DEBUGLEVEL > 2 ) timer_start ( & ti ) ; nbguessed = guess_roots ( nf ) ; if ( DEBUGLEVEL > 2 ) timer_printf ( & ti , " " , nbguessed ) ; if ( nbguessed == 2 ) return trivroots ( ) ; nfdegree = nf_get_degree ( nf ) ; fa = factoru ( nbguessed ) ; LP = gel ( fa , 1 ) ; l = lg ( LP ) ; LE = gel ( fa , 2 ) ; disc = nf_get_disc ( nf ) ; for ( i = 1 ; i < l ; i ++ ) { long p = LP [ i ] ; if ( p == 2 ) { long v , vnf , k ; if ( LE [ i ] == 1 ) continue ; vnf = vals ( nfdegree ) ; v = vali ( disc ) ; for ( k = minss ( LE [ i ] , vnf + 1 ) ; k >= 1 ; k -- ) if ( v >= nfdegree * ( k - 1 ) ) { nbguessed >>= LE [ i ] - k ; LE [ i ] = k ; break ; } } else { long v , vnf , k ; ulong r , q = udivuu_rem ( nfdegree , p - 1 , & r ) ; if ( r ) { nbguessed /= upowuu ( p , LE [ i ] ) ; LE [ i ] = 0 ; continue ; } vnf = u_lval ( q , p ) ; v = Z_lval ( disc , p ) ; for ( k = minss ( LE [ i ] , vnf + 1 ) ; k >= 0 ; k -- ) if ( v >= nfdegree * k - ( long ) q ) { nbguessed /= upowuu ( p , LE [ i ] - k ) ; LE [ i ] = k ; break ; } } } if ( DEBUGLEVEL > 2 ) timer_printf ( & ti , " " , nbguessed ) ; if ( nbguessed == 2 ) return trivroots ( ) ; av = avma ; T = nf_get_pol ( nf ) ; if ( eulerphiu_fact ( fa ) == ( ulong ) nfdegree ) { z = ZXirred_is_cyclo_translate ( T , uissquarefree_fact ( fa ) ) ; if ( DEBUGLEVEL > 2 ) timer_printf ( & ti , " " ) ; if ( z ) { z = nf_to_scalar_or_basis ( nf , z ) ; return gerepilecopy ( av , mkvec2 ( utoipos ( nbguessed ) , z ) ) ; } avma = av ; } nf_pick_prime_for_units ( nf , & L ) ; if ( DEBUGLEVEL > 2 ) timer_printf ( & ti , " " , L . p , L . Tp ? degpol ( L . Tp ) : 1 ) ; C0 = gmulsg ( nfdegree , L2_bound ( nf , gen_1 ) ) ; if ( DEBUGLEVEL > 2 ) err_printf ( " \n " , C0 ) ; bestlift_init ( ( long ) mybestlift_bound ( C0 ) , nf , C0 , & L ) ; L . dn = NULL ; if ( DEBUGLEVEL > 2 ) timer_start ( & ti ) ; nbroots = 2 ; z = gen_m1 ; q = powiu ( L . p , degpol ( L . Tp ) ) ; for ( i = 1 ; i < l ; i ++ ) { long k , p = LP [ i ] ; for ( k = minss ( LE [ i ] , Z_lval ( subiu ( q , 1UL ) , p ) ) ; k > 0 ; k -- ) { pari_sp av = avma ; long pk = upowuu ( p , k ) ; GEN r ; if ( pk == 2 ) continue ; r = nfcyclo_root ( pk , T , & L ) ; if ( DEBUGLEVEL > 2 ) timer_printf ( & ti , " " , p , k ) ; if ( r ) { if ( DEBUGLEVEL > 2 ) err_printf ( " \n " , uordinal ( pk ) ) ; if ( p == 2 ) { nbroots = pk ; z = r ; } else { nbroots *= pk ; z = nfmul ( nf , z , r ) ; } break ; } avma = av ; if ( DEBUGLEVEL ) pari_warn ( warner , " " ) ; } } return gerepilecopy ( av , mkvec2 ( utoi ( nbroots ) , z ) ) ; }
Number of roots of unity in number field [nf].
Number of roots of unity in number field [ nf ] .
/* Step 1 : guess number of roots and discard trivial case 2 */ /* Degree and ramification test: find largest k such that Q(zeta_{p^k})
     * may be a subfield of K. Q(zeta_p^k) has degree (p-1)p^(k-1)
     * and v_p(discriminant) = ((p-1)k-1)p^(k-1); so we must have
     * v_p(disc_K) >= ((p-1)k-1) * n / (p-1) = kn - q, where q = n/(p-1) */ /* the test simplifies a little in that case */ /* N.B the test above always works for k = 1: LE[i] >= 1 */ /* q = n/(p-1) */ /* N.B the test above always works for k = 0: LE[i] >= 0 */ /* Step 1.5 : test if nf.pol == subst(polcyclo(nbguessed), x, \pm x+c) */ /* Step 2 : choose a prime ideal for local lifting */ /* Step 3 : compute a reduced pr^k allowing lifting of local solutions */ /* evaluate maximum L2 norm of a root of unity in nf */ /* lift and reduce pr^k */ /* Step 4 : actual computation of roots */ /* for all prime power factors of nbguessed, find a p^k-th root of unity */ /* find p^k-th roots */ /* no need to test second roots ! */