sieve of eratosthenese for GF(2^

# sieve for irreducible polynomials of degree less than n. polynomials
# represented as integers with corresponding binary
# representations. zero and unit polynomials 0 and 1 excluded by
# convention

use integer;

my $n = 9;

my @c; # reducibles (composites)

for (my $k=2;$k<(1<<$n);$k++) {
    next if $c[$k];

    print "k=$k prime: ",polystr($k),"\n";

    for (my $j;$j<(1<<$n);$j++) {
	my $m = polyprod($k,$j);
#	print "(",polystr($k),")*(",polystr($j),")=",polystr($m),"\n";
	$c[$m] = 1 if ($m<(1<<$n));
    }
}

sub polystr($) {
    my $q = shift;
    return 0 if ($q == 0);
    return join("+",map { "x^$_"} grep { $q & (1<<$_) } 0..(2*$n-1));
}

sub polyprod($$) {
    my ($p1,$p2) = @_;
    my $s = 0;
    for (my $i=0;$i<$n;$i++) {
	$s ^= ($p2<<$i) if ($p1 & (1<<$i));
    }
    return $s;
}