bridge/class-master/depend/pari/src/basemath/base2.c
/* compute the characteristic polynomial of a/da mod chi (a in Z[X]), given
 * by its Newton sums to a precision of pp using Newton sums */
compute the characteristic polynomial of a/da mod chi (a in Z[X]), given
by its Newton sums to a precision of pp using Newton sums
compute the characteristic polynomial of a / da mod chi ( a in Z [ X ] ) given by its Newton sums to a precision of pp using Newton sums
static GEN
newtoncharpoly(GEN pp, GEN p, GEN NS)
{
  long n = lg(NS)-1, j, k;
  GEN c = cgetg(n + 2, t_VEC), pp2 = shifti(pp,-1);
  gel(c,1) = (n & 1 ? gen_m1: gen_1);
  for (k = 2; k <= n+1; k++)
  {
    pari_sp av2 = avma;
    GEN s = gen_0;
    ulong z;
    long v = u_pvalrem(k - 1, p, &z);
    for (j = 1; j < k; j++)
    {
      GEN t = mulii(gel(NS,j), gel(c,k-j));
      if (!odd(j)) t = negi(t);
      s = addii(s, t);
    }
    if (v) {
      s = gdiv(s, powiu(p, v));
      if (typ(s) != t_INT) return NULL;
    }
    s = mulii(s, Fp_inv(utoipos(z), pp));
    gel(c,k) = gerepileuptoint(av2, Fp_center_i(s, pp, pp2));
  }
  for (k = odd(n)? 1: 2; k <= n+1; k += 2) gel(c,k) = negi(gel(c,k));
  return gtopoly(c, 0);
}
static GEN newtoncharpoly ( GEN pp , GEN p , GEN NS ) { long n = lg ( NS ) - 1 , j , k ; GEN c = cgetg ( n + 2 , t_VEC ) , pp2 = shifti ( pp , -1 ) ; gel ( c , 1 ) = ( n & 1 ? gen_m1 : gen_1 ) ; for ( k = 2 ; k <= n + 1 ; k ++ ) { pari_sp av2 = avma ; GEN s = gen_0 ; ulong z ; long v = u_pvalrem ( k - 1 , p , & z ) ; for ( j = 1 ; j < k ; j ++ ) { GEN t = mulii ( gel ( NS , j ) , gel ( c , k - j ) ) ; if ( ! odd ( j ) ) t = negi ( t ) ; s = addii ( s , t ) ; } if ( v ) { s = gdiv ( s , powiu ( p , v ) ) ; if ( typ ( s ) != t_INT ) return NULL ; } s = mulii ( s , Fp_inv ( utoipos ( z ) , pp ) ) ; gel ( c , k ) = gerepileuptoint ( av2 , Fp_center_i ( s , pp , pp2 ) ) ; } for ( k = odd ( n ) ? 1 : 2 ; k <= n + 1 ; k += 2 ) gel ( c , k ) = negi ( gel ( c , k ) ) ; return gtopoly ( c , 0 ) ; }
compute the characteristic polynomial of a/da mod chi (a in Z[X]), given
 by its Newton sums to a precision of pp using Newton sums
compute the characteristic polynomial of a / da mod chi ( a in Z [ X ] ) given by its Newton sums to a precision of pp using Newton sums