bridge/class-master/depend/pari/src/basemath/galconj.c
/* return 0 if not galois or not wss */
return 0 if not galois or not wss
return 0 if not galois or not wss
static int
galoisanalysis(GEN T, struct galois_analysis *ga, long calcul_l)
{
  pari_sp ltop = avma, av;
  long group, linf, n, p, i, karma = 0;
  GEN F, Fp, Fe, Fpe, O;
  long np, order, plift, nbmax, nbtest, deg;
  pari_timer ti;
  forprime_t S;
  if (DEBUGLEVEL >= 1) timer_start(&ti);
  n = degpol(T);
  O = zero_zv(n);
  F = factoru_pow(n);
  Fp = gel(F,1); np = lg(Fp)-1;
  Fe = gel(F,2);
  Fpe= gel(F,3);
  group = init_group(n, np, Fp, Fe, &order);
  deg = Fp[np]; 
  plift = 0;
  nbtest = 0;
  nbmax = 8+(n>>1);
  u_forprime_init(&S, n*maxss(expu(n)-3, 2), ULONG_MAX);
  av = avma;
  while (!plift || (nbtest < nbmax && (nbtest <=8 || order < (n>>1)))
                || (n == 24 && O[6] == 0 && O[4] == 0)
                || ((group&ga_non_wss) && order == Fp[np]))
  {
    long d, o, norm_o = 1;
    GEN D, Tp;
    if ((group&ga_non_wss) && nbtest >= 3*nbmax) break; 
    nbtest++; avma = av;
    p = u_forprime_next(&S);
    if (!p) pari_err_OVERFLOW("galoisanalysis [ran out of primes]");
    Tp = ZX_to_Flx(T,p);
    if (!Flx_is_squarefree(Tp,p)) { if (!--nbtest) nbtest = 1; continue; }
    D = Flx_nbfact_by_degree(Tp, &d, p);
    o = n / d; 
    if (D[o] != d) { notgalois(p, ga); avma = ltop; return 0; }
    if (!O[o]) O[o] = p;
    if (o % deg) goto ga_end; 
    if ((group&ga_all_normal) && o < order) goto ga_end;
    if (o * Fp[1] >= n)
      norm_o = o; 
    else
    {
      for (i = np; i > 0; i--)
      {
        if (o % Fpe[i]) break;
        norm_o *= Fpe[i];
      }
    }
    if (norm_o != 1)
    {
      if (!(group&ga_all_normal) || o > order)
        karma = ugcd(p-1,n);
      else if (!improves(norm_o, deg, plift,p,n, &karma)) goto ga_end;
      deg = norm_o; group |= ga_all_normal; 
    }
    else if (group&ga_all_normal) goto ga_end;
    else if (!improves(o, order, plift,p,n, &karma)) goto ga_end;
    order = o; plift = p; 
    ga_end:
    if (DEBUGLEVEL >= 5)
      err_printf("GaloisAnalysis:Nbtest=%ld,p=%ld,o=%ld,n_o=%d,best p=%ld,ord=%ld,k=%ld\n", nbtest, p, o, norm_o, plift, order,karma);
  }
  ga->p = plift;
  if (!plift || ((group&ga_non_wss) && order == Fp[np]))
  {
    pari_warn(warner,"Galois group almost certainly not weakly super solvable");
    return 0;
  }
  linf = 2*n*usqrt(n);
  if (calcul_l && O[1] <= linf)
  {
    pari_sp av2;
    forprime_t S2;
    ulong p;
    u_forprime_init(&S2, linf+1,ULONG_MAX);
    av2 = avma;
    while ((p = u_forprime_next(&S2)))
    { 
      GEN Tp = ZX_to_Flx(T, p);
      long nb = Flx_nbroots(Tp, p);
      if (nb == n) { O[1] = p; break; }
      if (nb && Flx_is_squarefree(Tp,p)) {
        notgalois(p,ga);
        avma = ltop; return 0;
      }
      avma = av2;
    }
    if (!p) pari_err_OVERFLOW("galoisanalysis [ran out of primes]");
  }
  ga->group = (enum ga_code)group;
  ga->deg = deg;
  ga->mindeg =  n == 135 ? 15: 0; 
  ga->ord = order;
  ga->l  = O[1];
  ga->p4 = n >= 4 ? O[4] : 0;
  if (DEBUGLEVEL >= 4)
    err_printf("GaloisAnalysis:p=%ld l=%ld group=%ld deg=%ld ord=%ld\n",
               plift, O[1], group, deg, order);
  if (DEBUGLEVEL >= 1) timer_printf(&ti, "galoisanalysis()");
  avma = ltop; return 1;
}
static int galoisanalysis ( GEN T , struct galois_analysis * ga , long calcul_l ) { pari_sp ltop = avma , av ; long group , linf , n , p , i , karma = 0 ; GEN F , Fp , Fe , Fpe , O ; long np , order , plift , nbmax , nbtest , deg ; pari_timer ti ; forprime_t S ; if ( DEBUGLEVEL >= 1 ) timer_start ( & ti ) ; n = degpol ( T ) ; O = zero_zv ( n ) ; F = factoru_pow ( n ) ; Fp = gel ( F , 1 ) ; np = lg ( Fp ) - 1 ; Fe = gel ( F , 2 ) ; Fpe = gel ( F , 3 ) ; group = init_group ( n , np , Fp , Fe , & order ) ; deg = Fp [ np ] ; plift = 0 ; nbtest = 0 ; nbmax = 8 + ( n >> 1 ) ; u_forprime_init ( & S , n * maxss ( expu ( n ) - 3 , 2 ) , ULONG_MAX ) ; av = avma ; while ( ! plift || ( nbtest < nbmax && ( nbtest <= 8 || order < ( n >> 1 ) ) ) || ( n == 24 && O [ 6 ] == 0 && O [ 4 ] == 0 ) || ( ( group & ga_non_wss ) && order == Fp [ np ] ) ) { long d , o , norm_o = 1 ; GEN D , Tp ; if ( ( group & ga_non_wss ) && nbtest >= 3 * nbmax ) break ; nbtest ++ ; avma = av ; p = u_forprime_next ( & S ) ; if ( ! p ) pari_err_OVERFLOW ( " " ) ; Tp = ZX_to_Flx ( T , p ) ; if ( ! Flx_is_squarefree ( Tp , p ) ) { if ( ! -- nbtest ) nbtest = 1 ; continue ; } D = Flx_nbfact_by_degree ( Tp , & d , p ) ; o = n / d ; if ( D [ o ] != d ) { notgalois ( p , ga ) ; avma = ltop ; return 0 ; } if ( ! O [ o ] ) O [ o ] = p ; if ( o % deg ) goto ga_end ; if ( ( group & ga_all_normal ) && o < order ) goto ga_end ; if ( o * Fp [ 1 ] >= n ) norm_o = o ; else { for ( i = np ; i > 0 ; i -- ) { if ( o % Fpe [ i ] ) break ; norm_o *= Fpe [ i ] ; } } if ( norm_o != 1 ) { if ( ! ( group & ga_all_normal ) || o > order ) karma = ugcd ( p - 1 , n ) ; else if ( ! improves ( norm_o , deg , plift , p , n , & karma ) ) goto ga_end ; deg = norm_o ; group |= ga_all_normal ; } else if ( group & ga_all_normal ) goto ga_end ; else if ( ! improves ( o , order , plift , p , n , & karma ) ) goto ga_end ; order = o ; plift = p ; ga_end : if ( DEBUGLEVEL >= 5 ) err_printf ( " \n " , nbtest , p , o , norm_o , plift , order , karma ) ; } ga -> p = plift ; if ( ! plift || ( ( group & ga_non_wss ) && order == Fp [ np ] ) ) { pari_warn ( warner , " " ) ; return 0 ; } linf = 2 * n * usqrt ( n ) ; if ( calcul_l && O [ 1 ] <= linf ) { pari_sp av2 ; forprime_t S2 ; ulong p ; u_forprime_init ( & S2 , linf + 1 , ULONG_MAX ) ; av2 = avma ; while ( ( p = u_forprime_next ( & S2 ) ) ) { GEN Tp = ZX_to_Flx ( T , p ) ; long nb = Flx_nbroots ( Tp , p ) ; if ( nb == n ) { O [ 1 ] = p ; break ; } if ( nb && Flx_is_squarefree ( Tp , p ) ) { notgalois ( p , ga ) ; avma = ltop ; return 0 ; } avma = av2 ; } if ( ! p ) pari_err_OVERFLOW ( " " ) ; } ga -> group = ( enum ga_code ) group ; ga -> deg = deg ; ga -> mindeg = n == 135 ? 15 : 0 ; ga -> ord = order ; ga -> l = O [ 1 ] ; ga -> p4 = n >= 4 ? O [ 4 ] : 0 ; if ( DEBUGLEVEL >= 4 ) err_printf ( " \n " , plift , O [ 1 ] , group , deg , order ) ; if ( DEBUGLEVEL >= 1 ) timer_printf ( & ti , " " ) ; avma = ltop ; return 1 ; }
return 0 if not galois or not wss
return 0 if not galois or not wss
/*Now we study the orders of the Frobenius elements*/ /* largest prime | n */ /* in all cases */ /* d factors, all should have degree o */ /* NB: deg > 1 */ /*Frob_p has order o > 1, find a power which generates a normal subgroup*/ /*subgroups of smallest index are normal*/ /* Frob_p^(o/norm_o) generates a normal subgroup of order norm_o */ /* karma0=0, deg0<=norm_o -> the first improves() returns 1 */ /* STORE */ /* STORE */ /* To avoid looping on non-wss group.
   * TODO: check for large groups. Would it be better to disable this check if
   * we are in a good case (ga_all_normal && !(ga_ext_2) (e.g. 60)) ?*/ /*find a totally split prime l > linf*/ /* otherwise the second phase is too slow */