/* -*- 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 ====