bridge/class-master/depend/pari/src/basemath/mftrace.c
/* List of all square roots of -1 modulo N */
List of all square roots of -1 modulo N
List of all square roots of - 1 modulo N
static GEN
sqrtm1modN(long N)
{
  pari_sp av;
  GEN fa, P, E, B, mB, A, Q, T, R, v;
  long l, i, n, ct, fleven = 0;
  if ((N&3L) == 0) return cgetg(1,t_VECSMALL);
  if ((N&1L) == 0) { N >>= 1; fleven = 1; }
  fa = myfactoru(N); P = gel(fa,1); E = gel(fa,2);
  l = lg(P);
  for (i = 1; i < l; i++)
    if ((P[i]&3L) == 3) return cgetg(1,t_VECSMALL);
  A = cgetg(l, t_VECSMALL);
  B = cgetg(l, t_VECSMALL);
  mB= cgetg(l, t_VECSMALL);
  Q = cgetg(l, t_VECSMALL);
  for (i = 1; i < l; i++)
  {
    long p = P[i], e = E[i];
    Q[i] = upowuu(p,e);
    B[i] = itou( Zp_sqrt(gen_m1, utoipos(p), e) );
    mB[i]= Q[i] - B[i];
  }
  ct = 1 << (l-1);
  T = ZV_producttree(Q);
  R = ZV_chinesetree(Q,T);
  v = cgetg(ct+1, t_VECSMALL);
  av = avma;
  for (n = 1; n <= ct; n++)
  {
    long m = n-1, r;
    for (i = 1; i < l; i++)
    {
      A[i] = (m&1L)? mB[i]: B[i];
      m >>= 1;
    }
    r = itou( ZV_chinese_tree(A, Q, T, R) );
    if (fleven && !odd(r)) r += N;
    avma = av; v[n] = r;
  }
  return v;
}
static GEN sqrtm1modN ( long N ) { pari_sp av ; GEN fa , P , E , B , mB , A , Q , T , R , v ; long l , i , n , ct , fleven = 0 ; if ( ( N & 3L ) == 0 ) return cgetg ( 1 , t_VECSMALL ) ; if ( ( N & 1L ) == 0 ) { N >>= 1 ; fleven = 1 ; } fa = myfactoru ( N ) ; P = gel ( fa , 1 ) ; E = gel ( fa , 2 ) ; l = lg ( P ) ; for ( i = 1 ; i < l ; i ++ ) if ( ( P [ i ] & 3L ) == 3 ) return cgetg ( 1 , t_VECSMALL ) ; A = cgetg ( l , t_VECSMALL ) ; B = cgetg ( l , t_VECSMALL ) ; mB = cgetg ( l , t_VECSMALL ) ; Q = cgetg ( l , t_VECSMALL ) ; for ( i = 1 ; i < l ; i ++ ) { long p = P [ i ] , e = E [ i ] ; Q [ i ] = upowuu ( p , e ) ; B [ i ] = itou ( Zp_sqrt ( gen_m1 , utoipos ( p ) , e ) ) ; mB [ i ] = Q [ i ] - B [ i ] ; } ct = 1 << ( l - 1 ) ; T = ZV_producttree ( Q ) ; R = ZV_chinesetree ( Q , T ) ; v = cgetg ( ct + 1 , t_VECSMALL ) ; av = avma ; for ( n = 1 ; n <= ct ; n ++ ) { long m = n - 1 , r ; for ( i = 1 ; i < l ; i ++ ) { A [ i ] = ( m & 1L ) ? mB [ i ] : B [ i ] ; m >>= 1 ; } r = itou ( ZV_chinese_tree ( A , Q , T , R ) ) ; if ( fleven && ! odd ( r ) ) r += N ; avma = av ; v [ n ] = r ; } return v ; }
List of all square roots of -1 modulo N
List of all square roots of - 1 modulo N