bridge/class-master/depend/pari/src/basemath/nffactor.c
/* Guesses the number of roots of unity in number field [nf].
 * Computes gcd of N(P)-1 for some primes. The value returned is a proven
 * multiple of the correct value. */
Guesses the number of roots of unity in number field [nf].
Computes gcd of N(P)-1 for some primes. The value returned is a proven
multiple of the correct value.
Guesses the number of roots of unity in number field [ nf ] . Computes gcd of N ( P ) - 1 for some primes . The value returned is a proven multiple of the correct value .
static long
guess_roots(GEN nf)
{
  long c = 0, nfdegree = nf_get_degree(nf), B = nfdegree + 20, l;
  ulong p = 2;
  GEN T = nf_get_pol(nf), D = nf_get_disc(nf), index = nf_get_index(nf);
  GEN nbroots = NULL;
  forprime_t S;
  pari_sp av;
  (void)u_forprime_init(&S, 3, ULONG_MAX);
  av = avma;
  for (l=1; (p = u_forprime_next(&S)); l++)
  {
    GEN old, F, pf_1, Tp;
    long i, nb, gcdf = 0;
    if (!umodiu(D,p) || !umodiu(index,p)) continue;
    Tp = ZX_to_Flx(T,p); 
    F = Flx_nbfact_by_degree(Tp, &nb, p);
    for (i = 1; i <= nfdegree; i++)
      if (F[i]) {
        gcdf = gcdf? ugcd(gcdf, i): i;
        if (gcdf == 1) break;
      }
    pf_1 = subiu(powuu(p, gcdf), 1);
    old = nbroots;
    nbroots = nbroots? gcdii(pf_1, nbroots): pf_1;
    if (DEBUGLEVEL>5)
      err_printf("p=%lu; gcf(f(P/p))=%ld; nbroots | %Ps",p, gcdf, nbroots);
    if (old && equalii(nbroots,old))
    { if (!is_bigint(nbroots) && ++c > B) break; }
    else
      c = 0;
  }
  if (!nbroots) pari_err_OVERFLOW("guess_roots [ran out of primes]");
  if (DEBUGLEVEL>5) err_printf("%ld loops\n",l);
  avma = av; return itos(nbroots);
}
static long guess_roots ( GEN nf ) { long c = 0 , nfdegree = nf_get_degree ( nf ) , B = nfdegree + 20 , l ; ulong p = 2 ; GEN T = nf_get_pol ( nf ) , D = nf_get_disc ( nf ) , index = nf_get_index ( nf ) ; GEN nbroots = NULL ; forprime_t S ; pari_sp av ; ( void ) u_forprime_init ( & S , 3 , ULONG_MAX ) ; av = avma ; for ( l = 1 ; ( p = u_forprime_next ( & S ) ) ; l ++ ) { GEN old , F , pf_1 , Tp ; long i , nb , gcdf = 0 ; if ( ! umodiu ( D , p ) || ! umodiu ( index , p ) ) continue ; Tp = ZX_to_Flx ( T , p ) ; F = Flx_nbfact_by_degree ( Tp , & nb , p ) ; for ( i = 1 ; i <= nfdegree ; i ++ ) if ( F [ i ] ) { gcdf = gcdf ? ugcd ( gcdf , i ) : i ; if ( gcdf == 1 ) break ; } pf_1 = subiu ( powuu ( p , gcdf ) , 1 ) ; old = nbroots ; nbroots = nbroots ? gcdii ( pf_1 , nbroots ) : pf_1 ; if ( DEBUGLEVEL > 5 ) err_printf ( " " , p , gcdf , nbroots ) ; if ( old && equalii ( nbroots , old ) ) { if ( ! is_bigint ( nbroots ) && ++ c > B ) break ; } else c = 0 ; } if ( ! nbroots ) pari_err_OVERFLOW ( " " ) ; if ( DEBUGLEVEL > 5 ) err_printf ( " \n " , l ) ; avma = av ; return itos ( nbroots ) ; }
Guesses the number of roots of unity in number field [nf].
Guesses the number of roots of unity in number field [ nf ] .
/* result must be stationary (counter c) for at least B loops */ /* squarefree */ /* the gcd of the p^f - 1 is p^(gcd of the f's) - 1 */ /* if same result go on else reset the stop counter [c] */