/* Program to determine the smallest N for which a given mod-2 polynomial divides t^N+1. Author: M.V.Wickerhauser Date: 22 August 2002 */ #include void usage(const char *name, const char *msg) { fprintf(stderr, "usage: %s mod2poly \n ?? ", name); fputs(msg, stderr); fputc('\n', stderr); exit(1); } unsigned int least_power ( unsigned int mod2poly, int degree ) { unsigned int rem, mask, highbit, N; if(mod2poly%2==0) return 0; /* error: t divides mod2poly */ highbit = 0x1<<(degree-1); mask = highbit|(highbit-1); for(rem=mod2poly&mask, N=degree; rem!=0x1; ++N ) if( rem & highbit ) rem = ((rem<<1)^mod2poly) & mask; else rem <<= 1; return N; } int main ( int argc, char **argv ) { int degree; const char *bit; unsigned int mod2poly, N; /* Expect `mod2poly' as arg[1] on command line. */ if(argc!=2) usage(argv[0], "Needs a bitstring for mod2poly."); /* Convert and store the tail bits of mod2poly */ if(argv[1][0]!='1') usage(argv[0],"Leftmost bit of mod2poly must be 1."); bit = &argv[1][1]; /* all after the first bit */ mod2poly = 1; degree = 0; while(bit[degree]) { mod2poly = (mod2poly<<1)|(bit[degree]=='1'? 0x1 : 0x0); ++degree; } if(degree<2) usage(argv[0],"need degree(mod2poly)>1."); if(degree>32) usage(argv[0],"need degree(mod2poly)< 33."); N = least_power(mod2poly, degree); printf("Mod-2 polynomial %u = %s (base 2) divides t^%u+1\n", mod2poly, argv[1], N); return 0; }