/*
  fichier gene16.c
  fonction : cherche un trinôme générateur pour GF(2^16)
  compilation :
    gcc -Os -march=pentium3 -fomit-frame-pointer -o gene16 gene16.c
*/

#include <stdio.h>
#include <string.h>

 /* en raison de la faible longueur du cycle (64K max),
   on peut utiliser directement un tableau au lieu
   d'une méthode plus complexe : */
unsigned char compteurs[65536];

int main(void) {
  unsigned long int i, iteration;
  unsigned short int lfsr, mask;

  for (i=2; i<15; i++) {
    /* initialise les variables pour un tour */
    memset(&compteurs, 0, sizeof(compteurs));
    iteration=0;
    mask = (1 << i) | 1;
    lfsr=1; /* seed */

    while (!compteurs[lfsr]) {
      compteurs[lfsr] = 1;
      iteration++;

      /* calcul d'un pas de LFSR */
      lfsr = (lfsr+lfsr) ^ (mask & (((signed int)lfsr) >> 15));
    }

    printf("trinôme x^16 + x^%d + 1 : %d itérations\n",
      i, iteration);
  }

  return 0;
}