/* poly.c scans for maximal length LFSRs */
/* Steve Ungstad, 1997,98 */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

main(int argc, char *argv[]) {
	char key[80] ;
	int lin, l, j, q ;
	long unsigned int  p, r, n, t, m, i, tp ;
	if(argc!=2){
		printf("Usage:poly <length>\n"
               "Finds prs polynomials of maximum cycle length\n" 
               "Enter bit length (3-31) and continue(?): ");
        gets(key);
	    if(*key==0)exit(0);
	    sscanf(key,"%d", &l);
	    }      
	else {
        sscanf(argv[1],"%d", &l) ;
         };
	if((l < 2)||(l > 31)) {
	   fprintf(stderr,"length out of bounds\n");
	   exit(1);};
	if(l>22){printf("warning: >22 bits will take a while, continue? ");
	     gets(key);
	     if(*key=='q'||*key=='n') exit(0);
	      };
  /* t=10000....  m=FFFF.... l=length lin=number of lines to screen */
  /* q=number of solutions */
	t=(long)1 << l; m = t-1; lin=0;
	q=0;
  /* p=polynomial, 3=x^1+x^0, test all odd, ie must include x^0 */
	for(p=3;p<t;p=p+2){
	 r=2; n=1;
  /* find first power of 2 mod p that =1=2^(n=0) */
     tp= t|p;
	 while(r != 1){
	  n++;
	  r <<= 1;
	  if (r & t){ r ^= tp ;};
	 }
  /* n is cycle length and maximum=m */
	 if(n==m){
  /* add 1 to number of solutions, calculate reverse poly=i */
	   q++;
	   i=1;
	   for(j=1;j<l;j++){
		if(p & ((long)1<<j)) i|=(t >> j) ;
	   }; 
	   
	   printf("f(x) x^%d = 0x%lX,  reverse of 0x%lX\n", l, p, i);
 /* pause every 21 lines to screen, every line for large (slow) poly */
	   lin++;
	   if(lin>20||l>18){
	     lin=0;
	     printf("more:(q to quit)");
	     gets(key);
	     if(*key=='q') exit(0);
	   };
	 }
        }
	printf("number of solutions= %d\n",q);
        }