/*
  Author:  Pate Williams (c) 1997

  Exercise 1.8
  "There are eight different linear recurrences
  over Z_2 of degree four having c0 = 1. Deter-
  mine which of these recurrences give rise to
  a keystream of period 15 (given a non-zero
  initialization vector)." -Douglas R. Stinson-
  See "Cryptography: Theory and Practice" by
  Douglas R. Stinson page 42.
*/

#include <stdio.h>

int main(void)
{
  int found;
  long c0 = 1, c1, c2, c3, i, j, z[50];


  z[0] = 1, z[1] = z[2] = z[3] = 0;
  for (c1 = 0; c1 < 2; c1++) {
    for (c2 = 0; c2 < 2; c2++) {
      for (c3 = 0; c3 < 2; c3++) {
        printf("1%ld%ld%ld 1000", c1, c2, c3);
        for (i = 0; i < 32; i++) {
          z[i + 4] = (c0 * z[i] + c1 * z[i + 1] +
                      c2 * z[i + 2] + c3 * z[i + 3]) % 2;
          printf("%ld", z[i + 4]);
        }
        for (i = 2; i <= 15; i++) {
          found = 1;
          for (j = 0; found && j < i; j++)
            found = z[j] == z[j + i];
          if (found) {
            j = i;
            break;
          }
        }
        if (found) printf(" %ld\n", j);
      }
    }
  }
  return 0;
}