/* -*- gp-script -*- */ \\% Swan's theorem for reducibility of trinomal x^n+x^k+1 over GF(2) \\ Author: Joerg Arndt \\ License: GPL version 3 or later \\ online at http://www.jjj.de/pari/ \\ version: 2014-October-16 (18:30) swan_core(n,k)= { /* auxiliary routine for swan() */ my( n8 ); n8 = bitand(n,7); n8 = min(n8, 8-n8); if ( bitand(n,1)==0, /* n even */ if ( bitand(k,1), /* k odd */ if ( (n!=2*k) && (bitand((n*k)>>1, 3) <=1), return(1) ); ); , /* else (n odd) */ if ( bitand(k,1)==0, /* k even */ if ( (n8==3) && (((2*n)%k)!=0), return(1) ); if ( (n8==1) && (((2*n)%k)==0), return(1) ); ); ); return( 0 ); } /* ----- */ swan(n,k)= { /* Return whether trinomial x^n+x^k+1 over GF(2) is reducible by Swan's theorem */ if ( (bitand(n,1)==0) && (bitand(k,1)==0), return(1) ); /* poly is a square */ if ( (k==n) || (k==0), return(0) ); if ( k>n, return( swan(k,n) ) ); if ( swan_core(n,k)==1, return(1) ); return( swan_core(n,n-k) ); } /* ----- */ \\ ==== end of file ====