bridge/class-master/depend/pari/src/basemath/base2.c
/* if flag = 0, maximal order, else factorization to precision r = flag */
if flag = 0, maximal order, else factorization to precision r = flag
if flag = 0 maximal order else factorization to precision r = flag
static GEN
Decomp(decomp_t *S, long flag)
{
  pari_sp av = avma;
  GEN fred, pr2, pr, pk, ph2, ph, b1, b2, a, e, de, f1, f2, dt, th, chip;
  GEN p = S->p;
  long vde, vdt, k, r = maxss(flag, 2*S->df + 1);
  if (DEBUGLEVEL>5) err_printf("  entering Decomp: %Ps^%ld\n  f = %Ps\n",
                               p, r, S->f);
  else if (DEBUGLEVEL>2) err_printf("  entering Decomp\n");
  chip = FpX_red(S->chi, p);
  if (!FpX_valrem(chip, S->nu, p, &b1))
  {
    if (!p_is_prime(S)) pari_err_PRIME("Decomp",p);
    pari_err_BUG("Decomp (not a factor)");
  }
  b2 = FpX_div(chip, b1, p);
  a = FpX_mul(FpXQ_inv(b2, b1, p), b2, p);
  th = QpX_remove_denom(S->phi, p, &dt, &vdt);
  if (dt)
  {
    long dega = degpol(a);
    vde = dega * vdt;
    de = powiu(dt, dega);
    pr = mulii(p, de);
    a = FpX_rescale(a, dt, pr);
  }
  else
  {
    vde = 0;
    de = gen_1;
    pr = p;
  }
  e = FpX_FpXQ_eval(a, th, S->f, pr);
  update_den(p, &e, &de, &vde, NULL);
  pk = p; k = 1;
  while (k < r + vde)
  { 
    GEN D;
    pk = sqri(pk); k <<= 1;
    e = ZX_mul(ZX_sqr(e), Z_ZX_sub(mului(3,de), gmul2n(e,1)));
    de= mulii(de, sqri(de));
    vde *= 3;
    D = mulii(pk, de);
    e = FpX_rem(e, centermod(S->f, D), D); 
    update_den(p, &e, &de, &vde, NULL);
  }
  pr = powiu(p, r); pr2 = shifti(pr, -1);
  ph = mulii(de,pr);ph2 = shifti(ph, -1);
  fred = FpX_center_i(FpX_red(S->f, ph), ph, ph2);
  e    = FpX_center_i(FpX_red(e, ph), ph, ph2);
  f1 = ZpX_gcd(fred, Z_ZX_sub(de, e), p, ph); 
  fred = FpX_center_i(fred, pr, pr2);
  f1   = FpX_center_i(f1,   pr, pr2);
  f2 = FpX_div(fred,f1, pr);
  f2 = FpX_center_i(f2, pr, pr2);
  if (DEBUGLEVEL>5)
    err_printf("  leaving Decomp: f1 = %Ps\nf2 = %Ps\ne = %Ps\nde= %Ps\n", f1,f2,e,de);
  if (flag < 0)
  {
    GEN m = vconcat(ZpX_primedec(f1, p), ZpX_primedec(f2, p));
    return sort_factor(m, (void*)&cmpii, &cmp_nodata);
  }
  else if (flag)
  {
    gerepileall(av, 2, &f1, &f2);
    return shallowconcat(ZpX_monic_factor_squarefree(f1, p, flag),
                         ZpX_monic_factor_squarefree(f2, p, flag));
  } else {
    GEN D, d1, d2, B1, B2, M;
    long n, n1, n2, i;
    gerepileall(av, 4, &f1, &f2, &e, &de);
    D = de;
    B1 = get_partial_order_as_pols(p,f1); n1 = lg(B1)-1;
    B2 = get_partial_order_as_pols(p,f2); n2 = lg(B2)-1; n = n1+n2;
    d1 = QpXV_denom(B1);
    d2 = QpXV_denom(B2); if (cmpii(d1, d2) < 0) d1 = d2;
    if (d1 != gen_1) {
      B1 = Q_muli_to_int(B1, d1);
      B2 = Q_muli_to_int(B2, d1);
      D = mulii(d1, D);
    }
    fred = centermod_i(S->f, D, shifti(D,-1));
    M = cgetg(n+1, t_MAT);
    for (i=1; i<=n1; i++)
      gel(M,i) = RgX_to_RgC(FpX_rem(FpX_mul(gel(B1,i),e,D), fred, D), n);
    e = Z_ZX_sub(de, e); B2 -= n1;
    for (   ; i<=n; i++)
      gel(M,i) = RgX_to_RgC(FpX_rem(FpX_mul(gel(B2,i),e,D), fred, D), n);
    return ZpM_hnfmodid(M, p, D);
  }
}
static GEN Decomp ( decomp_t * S , long flag ) { pari_sp av = avma ; GEN fred , pr2 , pr , pk , ph2 , ph , b1 , b2 , a , e , de , f1 , f2 , dt , th , chip ; GEN p = S -> p ; long vde , vdt , k , r = maxss ( flag , 2 * S -> df + 1 ) ; if ( DEBUGLEVEL > 5 ) err_printf ( " \n \n " , p , r , S -> f ) ; else if ( DEBUGLEVEL > 2 ) err_printf ( " \n " ) ; chip = FpX_red ( S -> chi , p ) ; if ( ! FpX_valrem ( chip , S -> nu , p , & b1 ) ) { if ( ! p_is_prime ( S ) ) pari_err_PRIME ( " " , p ) ; pari_err_BUG ( " " ) ; } b2 = FpX_div ( chip , b1 , p ) ; a = FpX_mul ( FpXQ_inv ( b2 , b1 , p ) , b2 , p ) ; th = QpX_remove_denom ( S -> phi , p , & dt , & vdt ) ; if ( dt ) { long dega = degpol ( a ) ; vde = dega * vdt ; de = powiu ( dt , dega ) ; pr = mulii ( p , de ) ; a = FpX_rescale ( a , dt , pr ) ; } else { vde = 0 ; de = gen_1 ; pr = p ; } e = FpX_FpXQ_eval ( a , th , S -> f , pr ) ; update_den ( p , & e , & de , & vde , NULL ) ; pk = p ; k = 1 ; while ( k < r + vde ) { GEN D ; pk = sqri ( pk ) ; k <<= 1 ; e = ZX_mul ( ZX_sqr ( e ) , Z_ZX_sub ( mului ( 3 , de ) , gmul2n ( e , 1 ) ) ) ; de = mulii ( de , sqri ( de ) ) ; vde *= 3 ; D = mulii ( pk , de ) ; e = FpX_rem ( e , centermod ( S -> f , D ) , D ) ; update_den ( p , & e , & de , & vde , NULL ) ; } pr = powiu ( p , r ) ; pr2 = shifti ( pr , -1 ) ; ph = mulii ( de , pr ) ; ph2 = shifti ( ph , -1 ) ; fred = FpX_center_i ( FpX_red ( S -> f , ph ) , ph , ph2 ) ; e = FpX_center_i ( FpX_red ( e , ph ) , ph , ph2 ) ; f1 = ZpX_gcd ( fred , Z_ZX_sub ( de , e ) , p , ph ) ; fred = FpX_center_i ( fred , pr , pr2 ) ; f1 = FpX_center_i ( f1 , pr , pr2 ) ; f2 = FpX_div ( fred , f1 , pr ) ; f2 = FpX_center_i ( f2 , pr , pr2 ) ; if ( DEBUGLEVEL > 5 ) err_printf ( " \n \n \n \n " , f1 , f2 , e , de ) ; if ( flag < 0 ) { GEN m = vconcat ( ZpX_primedec ( f1 , p ) , ZpX_primedec ( f2 , p ) ) ; return sort_factor ( m , ( void * ) & cmpii , & cmp_nodata ) ; } else if ( flag ) { gerepileall ( av , 2 , & f1 , & f2 ) ; return shallowconcat ( ZpX_monic_factor_squarefree ( f1 , p , flag ) , ZpX_monic_factor_squarefree ( f2 , p , flag ) ) ; } else { GEN D , d1 , d2 , B1 , B2 , M ; long n , n1 , n2 , i ; gerepileall ( av , 4 , & f1 , & f2 , & e , & de ) ; D = de ; B1 = get_partial_order_as_pols ( p , f1 ) ; n1 = lg ( B1 ) - 1 ; B2 = get_partial_order_as_pols ( p , f2 ) ; n2 = lg ( B2 ) - 1 ; n = n1 + n2 ; d1 = QpXV_denom ( B1 ) ; d2 = QpXV_denom ( B2 ) ; if ( cmpii ( d1 , d2 ) < 0 ) d1 = d2 ; if ( d1 != gen_1 ) { B1 = Q_muli_to_int ( B1 , d1 ) ; B2 = Q_muli_to_int ( B2 , d1 ) ; D = mulii ( d1 , D ) ; } fred = centermod_i ( S -> f , D , shifti ( D , -1 ) ) ; M = cgetg ( n + 1 , t_MAT ) ; for ( i = 1 ; i <= n1 ; i ++ ) gel ( M , i ) = RgX_to_RgC ( FpX_rem ( FpX_mul ( gel ( B1 , i ) , e , D ) , fred , D ) , n ) ; e = Z_ZX_sub ( de , e ) ; B2 -= n1 ; for ( ; i <= n ; i ++ ) gel ( M , i ) = RgX_to_RgC ( FpX_rem ( FpX_mul ( gel ( B2 , i ) , e , D ) , fred , D ) , n ) ; return ZpM_hnfmodid ( M , p , D ) ; } }
if flag = 0, maximal order, else factorization to precision r = flag
if flag = 0 maximal order else factorization to precision r = flag
/* E = e / de, e in Z[X], de in Z,  E = a(phi) mod (f, p) */ /* E, (1 - E) tend to orthogonal idempotents in Zp[X]/(f) */ /* E <-- E^2(3-2E) mod p^2k, with E = e/de */ /* e/de defined mod pk */ /* required precision of the factors */ /* p-adic gcd(f, 1-e) */