/***************************************************************
 *                                                             *
 *   the purpose of this program is to see if polynomials with *
 *  polynomial coefficients can have primitive roots.  Both    *
 *  coefficients are GF(2^n) and the polynomial is GF((2^n)^m).*
 *  This problem was presented by a question on the ECC book   *
 *  forum.                                                     *
 *                       Author = Mike Rosing                  *
 *                       Date = Oct. 7, 2010                   *
 *                                                             *
 **************************************************************/

#include <stdio.h>

main()
{
  int poly[4], timesx[5];
  int i, j, mul[4][4];

/*  assume each coefficient has modulo w^2+1.
    See if patterns repeat when multiplying by x when starting
    from 1.
*/

  poly[3] = 1;  // x^3
  poly[2] = 1;  // + x^2
  poly[1] = 0;  // (no x)
  poly[0] = 2;  // + w  = x^4

/*  create multiplication table for coefficients  */

  for(i=0; i<4; i++)
    for(j=0; j<4; j++)
      mul[i][j] = 0;
  mul[1][1] = 1;
  mul[1][2] = 2;
  mul[2][1] = 2;
  mul[3][1] = 3;
  mul[1][3] = 3;
  mul[2][2] = 3;
  mul[2][3] = 1;
  mul[3][2] = 1;
  mul[3][3] = 2;

  for(i=0; i<5; i++) timesx[i] = 0;
  timesx[0] = 1;

  for( j=1; j<256; j++)
  {
    // multiply by x
    for(i=4; i>0; i--) timesx[i] = timesx[i-1];
    timesx[0] = 0;

    // if x^4 term shows up, take it modulo poly if it does

    if(timesx[4])
    {
      for(i=0; i<4; i++)
	timesx[i] ^= mul[timesx[4]][poly[i]];
      timesx[4] = 0;
    }

// reduce coefficients modulo w^2 + 1

    printf("%3d: ", j);
    for(i=3; i>=0; i--)
    {
      if(timesx[i] & 4) 
      {
	timesx[i] ^= 1;
	timesx[i] &= 3;
      }
      if(timesx[i] == 3) printf("w+1");
      else if(timesx[i] == 2) printf("w");
      else if(timesx[i] == 1) printf("1");
      else printf("0");
      printf(" | ");
    }
    printf("\n");
  }
}