/*
implementation of noam nisan's prng which fools all statistical tests in L.
uses NTL for GF(2^n) and GF(2^n)[x] arithmetic.

written by seth hardy, shardy@aculei.net

license-ish thing:
you can use this code if you give credit where credit is due.
I assume no responsibility for what happens if you use it, though.

*/ 


#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
#include <math.h>
#include <time.h>
#include <NTL/GF2X.h>
#include <NTL/GF2E.h>
#include <NTL/GF2XFactoring.h>

char buf = 0;
int pos = 0;

void R(FILE *, int, int, GF2E, GF2E[][2]);

int main(int argc, char **argv) {

  int t, k;
  GF2X irr;
  FILE *out;

  if( argc != 4 ) {
    printf("\nusage: %s wordsize levels filename\n\n",argv[0]);
    exit(1);
  }
 
  srandom(time(NULL));
  GF2X::HexOutput = 1;

  t = atoi(argv[1]);
  k = atoi(argv[2]);
  out = fopen(argv[3],"w");

  cout << "using field of size 2^" << t;
  cout << " and " << k << " levels of recursion." << endl;
 
  irr = BuildSparseIrred_GF2X(t);
  GF2E::init(irr);

  GF2E x;
  x = random_GF2E();
  cout << "random seed x: " << x << endl;

  GF2E h[64][2];

  for(int i=0;i<k;i++) {
    h[i][0] = random_GF2E();
    h[i][1] = random_GF2E();
  }

  cout << "random hash functions computed." << endl;

  R(out,t,k,x,h);

  fclose(out);
  cout << t * pow(2,k) << " pseudorandom bits generated." << endl;

  return(0);

}

void R(FILE *out, int t, int k, GF2E x, GF2E h[][2]) {

  GF2X r;
  GF2 c;

  //cout << "R(" << k << "," << x << ")" << endl;

  if( k < 0 ) {
    cout << "error, k needs to be nonnegative. (" << k << ")" << endl;
    exit(1);
  }
  
  if( k == 0 ) {
    r = rep(x);
    for(int i=0;i<t;i++) {
      c = coeff(r,i);
      buf <<= 1;
      pos++;
      if( IsOne(c) ) buf |= 0x01;
      if( pos == 8 ) {
        fprintf(out,"%c",buf);
        pos = 0;
        buf = 0;
      }
    }
    return;
  }

  R(out,t,k-1,x,h);
  R(out,t,k-1,x*h[k][1]+h[k][0],h);

}