\\% Order of polynomials over GF(2)
\\ Author: Joerg Arndt
\\ License: GPL version 3 or later
\\ online at http://www.jjj.de/pari/
\\ version: 2011-January-19 (12:49)

read("mersfact.gpi"); /* factorizations of mersenne numbers: mersfact() */

global(nn_, np_, vp_, vf_, vx_, vd_);
nn_ = 0;  /* max order  =  2^n-1 */
np_ = 0;  /* number of primes in factorization, ==1 for nn_ prime */
vp_ = []; /* vector of primes */
vf_ = []; /* vector of factors (prime powers) */
vx_ = []; /* vector of exponents */
vd_ = []; /* vector of differences nn_/pi */


setup_fact(n) =
/* Setup factorization of 2^n-1
 * Result is used for polorder() and polmaxorder_q()
 */
{
  local(t, f);

  nn_ = 2^n - 1;
/*  print(" #div=", numdiv(nn_));*/
/*  f = factorint(nn_);*/
  f = mersfact(n);
  if ( f==[], return([]) );  \\ factorization unknown

  t = mattranspose(vecextract(f,2));
  np_ = length(t);
/*  print(" #primes=" np_);*/
  vx_ = vector(np_, i, t[1, i]);
  t = mattranspose(vecextract(f,1));
  vp_ = vector(np_, i, t[1, i]);
  vf_ = vector(np_, i, vp_[i]^vx_[i]);

  vd_ = vector(np_, i, nn_/vp_[np_+1-i]);
  forstep (i=np_, 2, -1,  vd_[i]-=vd_[i-1] );

/*  print1("@",f,"\n");*/
/*  print("  vf_= ", vf_);*/
/*  print("  vp_= ", vp_);*/
/*  print("  vx_= ", vx_);*/
/*  print("  vd_= ", vd_);*/
    return( vp_ );  \\ prime factors
} /* ------------ */


polorder(p, g='x) =
/* Order of g modulo p (p irreducible over GF(2)) */
/* NOTE: must call setup_fact(n) first where n=poldegree(p) */
{
    local(g1, te, tp, tf, tx);
    p *= Mod(1,2);
    te = nn_;
    for(i=1, np_,
        tf = vf_[i];  tp = vp_[i];  tx = vx_[i];
        te = te / tf;
        g1 = Mod(g, p)^te;
        while ( 1!=g1,
            g1 = g1^tp;
            te = te * tp;
        );
    );

\\  print(" order=", te );
    return( te );
} /* ------------ */

polmaxorder_q(p, g='x) =
\\ Whether order of g modulo p is maximal
\\  (p must be irreducible over GF(2))
\\ Early-out variant 
\\ NOTE: must call setup_fact(n) first where n=poldegree(p)
{
    local(g1, te, tp, tf, tx, ct);
    p *= Mod(1,2);
    te = nn_;
    for(i=1, np_,
        tf = vf_[i];  tp = vp_[i];  tx = vx_[i];
        te = te / tf;
        g1 = Mod(g, p)^te;
        ct = 0;
        while ( 1!=g1,
            g1 = g1^tp;
\\            print(" :: ", lift( g1 ) );
            te = te * tp;
            ct = ct + 1;
        );
        if ( ct<tx,  return(0) );
    );
    return(1);
} /* ------------ */

polmaxorder_q2(p, g='x) =
\\ Whether order of g modulo p is maximal
\\  (p must be irreducible over GF(2))
\\ Variant using difference vector 
\\ NOTE: must call setup_fact(n) first where n=poldegree(p)
{
    local(gm, g1);
    gm = Mod(g, p);
    g1 = Mod(1, p);
    for (j=1, np_,
        g1 *= ( gm^vd_[j] );
\\        print(" :: ", lift( lift(g1) ) );
        if ( 1==g1, return( 0 ) );
    );
    return( 1 );
} /* ------------ */

\\ ==== end of file ====