/* -*- gp-script -*- */ \\% Order of polynomials over GF(2) \\ Author: Joerg Arndt \\ License: GPL version 3 or later \\ online at http://www.jjj.de/pari/ \\ version: 2019-May-04 (12:27) read("mersfact.gpi"); /* factorizations of mersenne numbers: mersfact() */ global(ne_, nn_, np_, vp_, vf_, vx_, vd_); ne_ = 0; /* the exponent */ nn_ = 0; /* max order = 2^ne - 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() */ { my(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)) */ { my(g1, te, tp, tf, tx); /* set up Mersenne factorization if needed: */ if ( poldegree(p) != ne_, setup_fact( poldegree(p) ) ); 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 { my(g1, te, tp, tf, tx, ct); /* set up Mersenne factorization if needed: */ if ( poldegree(p) != ne_, setup_fact( poldegree(p) ) ); 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