bridge/class-master/depend/pari/src/basemath/char.c
/* g of order o in abelian group G attached to cyc. Is g a minimal generator
 * [wrt lex order] of the cyclic subgroup it generates;
 * coprime = coprimes_zv(o) */
g of order o in abelian group G attached to cyc. Is g a minimal generator
[wrt lex order] of the cyclic subgroup it generates;
coprime = coprimes_zv(o)
g of order o in abelian group G attached to cyc . Is g a minimal generator [ wrt lex order ] of the cyclic subgroup it generates ; coprime = coprimes_zv ( o )
long
zv_cyc_minimal(GEN cyc, GEN g, GEN coprime)
{
  pari_sp av = avma;
  long i, maxi, d, k, e, l = lg(g), o = lg(coprime)-1; 
  GEN gd, gk;
  if (o == 1) return 1;
  for (k = 1; k < l; k++)
    if (g[k]) break;
  if (g[k] == 1) return 1;
  if (cyc[k] % g[k]) return 0;
  d = cyc[k] / g[k]; 
  for (k++; k < l; k++) 
    if (g[k]) break;
  if (k == l) return 1;
  cyc = vecslice(cyc,k,l-1);
  g   = vecslice(g,  k,l-1);
  e = cyc[1];
  gd = Flv_Fl_mul(g, d, e); maxi = e/ugcd(d,e);
  for (gk = g, k = d+1, i = 1; i < maxi; i++, k += d)
  {
    long ko = k % o;
    gk = Flv_add(gk, gd, e); if (!coprime[ko]) continue;
    gk = vecmoduu(gk, cyc);
    if (vecsmall_lexcmp(gk, g) < 0) { avma = av; return 0; }
  }
  avma = av; return 1;
}
long zv_cyc_minimal ( GEN cyc , GEN g , GEN coprime ) { pari_sp av = avma ; long i , maxi , d , k , e , l = lg ( g ) , o = lg ( coprime ) - 1 ; GEN gd , gk ; if ( o == 1 ) return 1 ; for ( k = 1 ; k < l ; k ++ ) if ( g [ k ] ) break ; if ( g [ k ] == 1 ) return 1 ; if ( cyc [ k ] % g [ k ] ) return 0 ; d = cyc [ k ] / g [ k ] ; for ( k ++ ; k < l ; k ++ ) if ( g [ k ] ) break ; if ( k == l ) return 1 ; cyc = vecslice ( cyc , k , l - 1 ) ; g = vecslice ( g , k , l - 1 ) ; e = cyc [ 1 ] ; gd = Flv_Fl_mul ( g , d , e ) ; maxi = e / ugcd ( d , e ) ; for ( gk = g , k = d + 1 , i = 1 ; i < maxi ; i ++ , k += d ) { long ko = k % o ; gk = Flv_add ( gk , gd , e ) ; if ( ! coprime [ ko ] ) continue ; gk = vecmoduu ( gk , cyc ) ; if ( vecsmall_lexcmp ( gk , g ) < 0 ) { avma = av ; return 0 ; } } avma = av ; return 1 ; }
g of order o in abelian group G attached to cyc.
g of order o in abelian group G attached to cyc .
/* elt order */ /* > 1 */ /* skip following 0s */ /* find k in (Z/e)^* such that g*k mod cyc is lexicographically minimal,
   * k = 1 mod d to fix the first non-zero entry */