typedef unsigned long int L;
#include <stdio.h>
#include <stdlib.h>
char irrp[] = {0, 1, 3, 3, 3, 5, 3, 3, 27, 3, 9, 5, 9, 27, 33, 3, 43,
  9, 9, 39, 9, 5, 3, 33, 27, 9, 27, 39, 3, 5, 3, 9, 141, 75, 27, 5, 53,
  63, 99, 17, 57, 9, 39, 89, 33, 27, 3, 33, 45, 113, 29, 75, 9, 71, 125,
  71, 149, 17, 99, 123, 3, 39, 105, 3, 27};
int q; // number of bits in an L.
L irp;
// pmul is the polynomial multiply for low 64 bits.
L pmul(L a, L b){L sm=0;
  while(b) {if(b&1) sm ^= a; a = a<<1; b>>=1;} return sm;}
// fmul is the field multiply.
L fmul(L a, L b){L ts=1L<<(q-1); L sm=0;
  while(b) {if(b&1) sm ^= a; a = (a<<1)^(a&ts?irp:0); b>>=1;}
  return sm&((1L<<q)-1);}
typedef struct{L q; L r;} PR;

int High(L x){int y=0; // position of most significant bit.
{int k=6; while(k--) {int p = 1<<k; if(x&-1L<<p) {x >>= p; y += p;}}}
return y;}

PR pqr(L n, L d){if(!d) exit(printf("foss\n")); // synthetic division
  int hn = High(n), hd = High(d); L a=0;
  int k = hn-hd; while(k>=0) {if(n&(1L<<(hn--))) {n ^= d<<k; a |= 1L<<k;} --k;}
  return (PR){a, n};}

PR ge(L a, L b) // Extended Euclidean Algorithm for GF(2^q)
// After http://cap-lore.com/code/Scheme/repository/egcd
{if (!b) return (PR){1, 0};
 PR qr = pqr(a, b);
 if(!qr.r) return (PR){0, 1};
 PR c = ge(b, qr.r);
 return (PR){c.r, c.q ^ pmul(c.r, qr.q)};}
#include <assert.h>
L rn(){int k=q; L j=0; while(k>30) {j = (j<<31) | random(); k -= 31;}
   return (j<<k)|(random()&((1L<<k)-1));}
L finv(L x){return ge(irp|(1L<<q), x).r;}
// void ti(L x){assert(fmul(x, finv(x)) == 1);}
void ti(L x){if(!(fmul(x, finv(x)) == 1)) exit(printf("inv! %lx %lx\n", x, finv(x)));}

int main(){for(q=1; q<64; ++q) {irp = irrp[q]&255;
  
  if(1) {int w=100000; while(w--){L a = rn(), b = rn(), c = rn();
    assert(fmul(fmul(a, b), c) == fmul(a, fmul(b, c)));
    assert(fmul(a, b) == fmul(b, a));
    assert(fmul(a, b^c) == (fmul(a, b)^fmul(a, c)));}}
  if(1) {int w = 100000; while(w--) {int nbc = 1+random()%q, dbc = random()%nbc;
    L n = random()&((1L<<nbc)-1)|(1L<<nbc), d = random()&((1L<<dbc)-1)|(1L<<dbc);
    PR r = pqr(n, d); assert((pmul(d, r.q)^r.r) == n);}}
  if(q<18) {{int k; for(k=1; k<(1L<<q); ++k) ti(k);}
      {char m[1<<q]; {int y=1<<q; while(y--) m[y]=0;} // no quardatic non-residues
        {int y=1<<q; while(y--) m[fmul(y, y)] = 1;}
        {int y=1<<q; while(y--) if(!m[y]) exit(printf("Bxx\n"));}}}
  else {int w = 100000; while(w--) {L x = rn(); if(x) ti(x);}}
  printf("%d OK\n", q);}
return 0;}

// 'f/ = (lambda (a) (trim (cdr (pegcd f a)))) where f is the irreducible poly.
// The value returned by pegcd is the x such that for some y, yf+xa = 1.
// The arithmetic above is the polynomial ring.
/* (let* ((F2 ((fileVal "finiteField") 2))(p->i (F2 'p->i)))
   (((fileVal "Do") 'DoL) 64 (lambda (L) (let ((q (+ L 1)))
     (- (p->i ((F2 'gfip) q)) (expt 2 q)))))) */