/* Program to test whether a polynomial modulo 2 is irreducible. */

#include <assert.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>

typedef unsigned long long int poly2;
#define ULL1  ((unsigned long long int)1) 

int
deg2 ( poly2 p )			/* return degree of p */
{
  int d= -1;			/* -1 signifies degree = -infinity */
  while(p>0) { ++d; p>>=1; }
  return d;
}

void
divide2 ( poly2 numer, poly2 denom, poly2 *quot, poly2 *rem )
{
  int shift;
  poly2 result=0;

  assert(denom>0);  assert(quot);  assert(rem);
  
  while( (shift=deg2(numer)-deg2(denom)) >= 0 ) {
    numer ^= denom<<shift;
    result |= ULL1<<shift;
  }
  *quot = result;
  *rem = numer;
  return;
}

poly2
multiply2 ( poly2 x, poly2 y )		/* return x times y in GF2 */
{
  int shift=0;
  poly2 result=0;

  while(x>0) {
    if( x&1 )
      result ^=(y<<shift);
    ++shift;			/* to consider next digit of x */
    x>>=1;			/* put the next bit of x at position 0 */
  }
  return result;
}

void
usage(const char *name)
{
  fprintf(stderr, "usage:  %s base[ 2 || 10 ] poly\n", name);
  exit(1);
}

int
main ( int argc, char **argv )
{
  poly2 x=0, y=1,  quot=1, rem=0;
  int base, reducible;
  char buf[1000]={0}, *endptr=buf+999;

  reducible = 0;		/* Not reducible unless a factor is found */

  if(argc!=3) usage(argv[0]);	/* expect `x' as arg[2] on command line. */
  errno=0;
  base=strtol(argv[1], 0, 10);	/* Accept `x' as base 10 or base 2 string */
  if(errno) { perror(0); exit(2); }

  errno=0;
  switch(base){
  default:    usage(argv[0]); break;
  case 2:
    x = strtoull(argv[2], 0, 2); /* read command line bitstring into `x' */
    break;
  case 10:
    x = strtoull(argv[2], 0,10); /* read command line number into `x' */
    break;
  }
  if(errno) { perror(0); exit(2); }

  printf("Testing polynomial %s (base 10):\n",ulltostr(x,endptr));
  fflush(stdout);

  for(y=2; y<=(ULL1<<(1+deg2(x)/2)); y++ ) /* check polys up to sqrt(x) */
    {
      divide2(x,y, &quot, &rem);
      if(rem==0) {
	printf("Poly %10lu divides, with quotient %s\n",
	       (unsigned long)y, ulltostr(quot,endptr));
	fflush(stdout); *endptr=0;
	reducible = 1;
      }
    }
  printf("==> Polynomial %s is %sreducible\n",
	 ulltostr(x,endptr), reducible?"":"ir");

  return 0;
}