/* -*- gp-script -*- */
\\% Testing irreducibility over GF(2)
\\ Author: Joerg Arndt
\\ License: GPL version 3 or later
\\ online at http://www.jjj.de/pari/
\\ version: 2014-October-16 (18:31)
polirred2_rabin(c)=
{ /* Return whether polynomial (in x) is irreducible over GF(2) */
/* Rabin's test. */
/* NOTE this routine is slower than the built-in routine */
my(d, f, np, p, e, X, m, g, ns);
d = poldegree(c);
c *= Mod(1,2);
if ( c=='x, return(1) ); \\ 'x' is irreducible
if ( 0==polcoeff(c,0), return(0)); \\ reducible
if ( d<1, return(0) ); \\ '0' and '1' are not irreducible
if ( 1!=gcd(c, deriv(c,'x)), return(0)); \\ reducible
ns = 0; \\ numbers of squarings so far
m = Mod( Mod(1,2) * 'x, c);
if ( ! isprime(d), \\ only if composite
f = factor(d);
\\ print(" f==",f);
np = matsize(f)[1]; \\ number of prime divisors
\\ if ( 0!=m^(2^d)-'x, return(0) ); \\ reducible
forstep (k=np, 1, -1, \\ biggest prime factor first
p = f[k,1]; \\ prime divisor
\\ print1(" ",d,"^[[", p,"]] ");
e = d/p;
\\ for (j=1, e-ns, m = sqr(m) );
m = m^(2^(e-ns));
\\ here: m == Mod('x,c)^(2^e);
ns = e;
\\ g = gcd(component(m,2)-'x, c);
g = gcd(lift(m)-'x, c);
\\ print1(" <>\n");
if ( 1!=g, return(0) ); \\ reducible
);
);
\\ for (j=1, d-ns, m = sqr(m) );
m = m^(2^(d-ns));
\\ here: m == Mod('x,c)^(2^d);
\\ print1(" <>\n");
if ( 0!=m-'x, return(0) ); \\ reducible
return( 1 ); \\ irreducible
} /* ----- */
polirred2_benor(c)=
{ /* Return whether polynomial (in x) is irreducible over GF(2) */
/* Ben-Or test. */
/* NOTE this routine is usually slower than the built-in routine */
my(h, u, upx, g);
c *= Mod(1,2);
if ( c=='x, return(1) ); \\ 'x' is irreducible
if ( 0==polcoeff(c,0), return(0)); \\ reducible
if ( poldegree(c)<1, return(0) ); \\ '0' and '1' are not irreducible
if ( 1!=gcd(c, deriv(c,'x)), return(0)); \\ reducible
h = floor( poldegree(c)/2 );
u = Mod(Mod(1,2) * 'x, c);
for (k=1, h,
u = sqr(u);
upx = u + 'x;
\\ g = gcd( component(upx,2), c);
g = gcd( lift(upx), c);
if ( 1!=g, return(0) ); \\ reducible
);
return(1); \\ irreducible
} /* ----- */
/*
Timing:
--- 1000 polynomials of degree 20:
time = 97 ms \\ built-in
time = 126 ms. \\ Rabin
time = 101 ms. \\ Ben-Or
--- 1000 polynomials of degree 50:
time = 436 ms \\ built-in
time = 974 ms. \\ Rabin
time = 473 ms. \\ Ben-Or
--- 100 polynomials of degree 100:
time = 138 ms. \\ built-in
time = 535 ms. \\ Rabin
time = 94 ms. \\ Ben-Or
--- 100 polynomials of degree 200:
time = 594 ms. \\ built-in
time = 2,779 ms. \\ Rabin
time = 1,008 ms. \\ Ben-Or
--- 100 polynomials of degree 300:
time = 1,501 ms. \\ built-in
time = 6,694 ms. \\ Rabin
time = 2,089 ms. \\ Ben-Or
--- 100 polynomials of degree 400:
time = 2,805 ms. \\ built-in
time = 20,398 ms. \\ Rabin
time = 4,110 ms. \\ Ben-Or
--- 100 polynomials of degree 500:
time = 5,004 ms. \\ built-in
time = 37,909 ms. \\ Rabin
time = 1,832 ms. \\ Ben-Or
--- 20 polynomials of degree 1000:
time = 5,335 ms. \\ built-in
time = 20,198 ms. \\ Rabin
time = 35 ms. \\ Ben-Or
--- 20 polynomials of degree 1001:
time = 6,247 ms. \\ built-in
time = 41,943 ms. \\ Rabin
time = 53 ms. \\ Ben-Or
--- 20 polynomials of degree 1009:
time = 6,186 ms. \\ built-in
time = 92,518 ms. \\ Rabin
time = 27 ms. \\ Ben-Or
*/
\\ ==== end of file ====