bcprov/src/main/java/org/bouncycastle/pqc/math/linearalgebra/GF2nPolynomialField.java - platform/external/bouncycastle - Git at Google

 package org.bouncycastle.pqc.math.linearalgebra;


 import java.security.SecureRandom;
 import java.util.Vector;


 /**
  * This class implements the abstract class <tt>GF2nField</tt> for polynomial
  * representation. It computes the field polynomial and the squaring matrix.
  * GF2nField is used by GF2nPolynomialElement which implements the elements of
  * this field.
  *
  * @see GF2nField
  * @see GF2nPolynomialElement
  */
 public class GF2nPolynomialField
     extends GF2nField
 {

     /**
      * Matrix used for fast squaring
      */
     GF2Polynomial[] squaringMatrix;

     // field polynomial is a trinomial
     private boolean isTrinomial = false;

     // field polynomial is a pentanomial
     private boolean isPentanomial = false;

     // middle coefficient of the field polynomial in case it is a trinomial
     private int tc;

     // middle 3 coefficients of the field polynomial in case it is a pentanomial
     private int[] pc = new int[3];

     /**
      * constructs an instance of the finite field with 2<sup>deg</sup>
      * elements and characteristic 2.
      *
      * @param deg the extention degree of this field
      * @param random     source of randomness for generating new polynomials.
      */
     public GF2nPolynomialField(int deg, SecureRandom random)
     {
         super(random);

         if (deg < 3)
         {
             throw new IllegalArgumentException("k must be at least 3");
         }
         mDegree = deg;
         computeFieldPolynomial();
         computeSquaringMatrix();
         fields = new Vector();
         matrices = new Vector();
     }

     /**
      * constructs an instance of the finite field with 2<sup>deg</sup>
      * elements and characteristic 2.
      *
      * @param deg  the degree of this field
      * @param random     source of randomness for generating new polynomials.
      * @param file true if you want to read the field polynomial from the
      *             file false if you want to use a random fielpolynomial
      *             (this can take very long for huge degrees)
      */
     public GF2nPolynomialField(int deg, SecureRandom random, boolean file)
     {
         super(random);

         if (deg < 3)
         {
             throw new IllegalArgumentException("k must be at least 3");
         }
         mDegree = deg;
         if (file)
         {
             computeFieldPolynomial();
         }
         else
         {
             computeFieldPolynomial2();
         }
         computeSquaringMatrix();
         fields = new Vector();
         matrices = new Vector();
     }

     /**
      * Creates a new GF2nField of degree <i>i</i> and uses the given
      * <i>polynomial</i> as field polynomial. The <i>polynomial</i> is checked
      * whether it is irreducible. This can take some time if <i>i</i> is huge!
      *
      * @param deg        degree of the GF2nField
      * @param random     source of randomness for generating new polynomials.
      * @param polynomial the field polynomial to use
      */
     public GF2nPolynomialField(int deg, SecureRandom random, GF2Polynomial polynomial)
         throws RuntimeException
     {
         super(random);

         if (deg < 3)
         {
             throw new IllegalArgumentException("degree must be at least 3");
         }
         if (polynomial.getLength() != deg + 1)
         {
             throw new RuntimeException();
         }
         if (!polynomial.isIrreducible())
         {
             throw new RuntimeException();
         }
         mDegree = deg;
         // fieldPolynomial = new Bitstring(polynomial);
         fieldPolynomial = polynomial;
         computeSquaringMatrix();
         int k = 2; // check if the polynomial is a trinomial or pentanomial
         for (int j = 1; j < fieldPolynomial.getLength() - 1; j++)
         {
             if (fieldPolynomial.testBit(j))
             {
                 k++;
                 if (k == 3)
                 {
                     tc = j;
                 }
                 if (k <= 5)
                 {
                     pc[k - 3] = j;
                 }
             }
         }
         if (k == 3)
         {
             isTrinomial = true;
         }
         if (k == 5)
         {
             isPentanomial = true;
         }
         fields = new Vector();
         matrices = new Vector();
     }

     /**
      * Returns true if the field polynomial is a trinomial. The coefficient can
      * be retrieved using getTc().
      *
      * @return true if the field polynomial is a trinomial
      */
     public boolean isTrinomial()
     {
         return isTrinomial;
     }

     /**
      * Returns true if the field polynomial is a pentanomial. The coefficients
      * can be retrieved using getPc().
      *
      * @return true if the field polynomial is a pentanomial
      */
     public boolean isPentanomial()
     {
         return isPentanomial;
     }

     /**
      * Returns the degree of the middle coefficient of the used field trinomial
      * (x^n + x^(getTc()) + 1).
      *
      * @return the middle coefficient of the used field trinomial
      */
     public int getTc()
         throws RuntimeException
     {
         if (!isTrinomial)
         {
             throw new RuntimeException();
         }
         return tc;
     }

     /**
      * Returns the degree of the middle coefficients of the used field
      * pentanomial (x^n + x^(getPc()[2]) + x^(getPc()[1]) + x^(getPc()[0]) + 1).
      *
      * @return the middle coefficients of the used field pentanomial
      */
     public int[] getPc()
         throws RuntimeException
     {
         if (!isPentanomial)
         {
             throw new RuntimeException();
         }
         int[] result = new int[3];
         System.arraycopy(pc, 0, result, 0, 3);
         return result;
     }

     /**
      * Return row vector i of the squaring matrix.
      *
      * @param i the index of the row vector to return
      * @return a copy of squaringMatrix[i]
      * @see GF2nPolynomialElement#squareMatrix
      */
     public GF2Polynomial getSquaringVector(int i)
     {
         return new GF2Polynomial(squaringMatrix[i]);
     }

     /**
      * Compute a random root of the given GF2Polynomial.
      *
      * @param polynomial the polynomial
      * @return a random root of <tt>polynomial</tt>
      */
     protected GF2nElement getRandomRoot(GF2Polynomial polynomial)
     {
         // We are in B1!!!
         GF2nPolynomial c;
         GF2nPolynomial ut;
         GF2nElement u;
         GF2nPolynomial h;
         int hDegree;
         // 1. Set g(t) <- f(t)
         GF2nPolynomial g = new GF2nPolynomial(polynomial, this);
         int gDegree = g.getDegree();
         int i;

         // 2. while deg(g) > 1
         while (gDegree > 1)
         {
             do
             {
                 // 2.1 choose random u (element of) GF(2^m)
                 u = new GF2nPolynomialElement(this, random);
                 ut = new GF2nPolynomial(2, GF2nPolynomialElement.ZERO(this));
                 // 2.2 Set c(t) <- ut
                 ut.set(1, u);
                 c = new GF2nPolynomial(ut);
                 // 2.3 For i from 1 to m-1 do
                 for (i = 1; i <= mDegree - 1; i++)
                 {
                     // 2.3.1 c(t) <- (c(t)^2 + ut) mod g(t)
                     c = c.multiplyAndReduce(c, g);
                     c = c.add(ut);
                 }
                 // 2.4 set h(t) <- GCD(c(t), g(t))
                 h = c.gcd(g);
                 // 2.5 if h(t) is constant or deg(g) = deg(h) then go to
                 // step 2.1
                 hDegree = h.getDegree();
                 gDegree = g.getDegree();
             }
             while ((hDegree == 0) || (hDegree == gDegree));
             // 2.6 If 2deg(h) > deg(g) then set g(t) <- g(t)/h(t) ...
             if ((hDegree << 1) > gDegree)
             {
                 g = g.quotient(h);
             }
             else
             {
                 // ... else g(t) <- h(t)
                 g = new GF2nPolynomial(h);
             }
             gDegree = g.getDegree();
         }
         // 3. Output g(0)
         return g.at(0);

     }

     /**
      * Computes the change-of-basis matrix for basis conversion according to
      * 1363. The result is stored in the lists fields and matrices.
      *
      * @param B1 the GF2nField to convert to
      * @see "P1363 A.7.3, p111ff"
      */
     protected void computeCOBMatrix(GF2nField B1)
     {
         // we are in B0 here!
         if (mDegree != B1.mDegree)
         {
             throw new IllegalArgumentException(
                 "GF2nPolynomialField.computeCOBMatrix: B1 has a different "
                     + "degree and thus cannot be coverted to!");
         }
         if (B1 instanceof GF2nONBField)
         {
             // speedup (calculation is done in PolynomialElements instead of
             // ONB)
             B1.computeCOBMatrix(this);
             return;
         }
         int i, j;
         GF2nElement[] gamma;
         GF2nElement u;
         GF2Polynomial[] COBMatrix = new GF2Polynomial[mDegree];
         for (i = 0; i < mDegree; i++)
         {
             COBMatrix[i] = new GF2Polynomial(mDegree);
         }

         // find Random Root
         do
         {
             // u is in representation according to B1
             u = B1.getRandomRoot(fieldPolynomial);
         }
         while (u.isZero());

         // build gamma matrix by multiplying by u
         if (u instanceof GF2nONBElement)
         {
             gamma = new GF2nONBElement[mDegree];
             gamma[mDegree - 1] = GF2nONBElement.ONE((GF2nONBField)B1);
         }
         else
         {
             gamma = new GF2nPolynomialElement[mDegree];
             gamma[mDegree - 1] = GF2nPolynomialElement
                 .ONE((GF2nPolynomialField)B1);
         }
         gamma[mDegree - 2] = u;
         for (i = mDegree - 3; i >= 0; i--)
         {
             gamma[i] = (GF2nElement)gamma[i + 1].multiply(u);
         }
         if (B1 instanceof GF2nONBField)
         {
             // convert horizontal gamma matrix by vertical Bitstrings
             for (i = 0; i < mDegree; i++)
             {
                 for (j = 0; j < mDegree; j++)
                 {
                     // TODO remember: ONB treats its Bits in reverse order !!!
                     if (gamma[i].testBit(mDegree - j - 1))
                     {
                         COBMatrix[mDegree - j - 1].setBit(mDegree - i - 1);
                     }
                 }
             }
         }
         else
         {
             // convert horizontal gamma matrix by vertical Bitstrings
             for (i = 0; i < mDegree; i++)
             {
                 for (j = 0; j < mDegree; j++)
                 {
                     if (gamma[i].testBit(j))
                     {
                         COBMatrix[mDegree - j - 1].setBit(mDegree - i - 1);
                     }
                 }
             }
         }

         // store field and matrix for further use
         fields.addElement(B1);
         matrices.addElement(COBMatrix);
         // store field and inverse matrix for further use in B1
         B1.fields.addElement(this);
         B1.matrices.addElement(invertMatrix(COBMatrix));
     }

     /**
      * Computes a new squaring matrix used for fast squaring.
      *
      * @see GF2nPolynomialElement#square
      */
     private void computeSquaringMatrix()
     {
         GF2Polynomial[] d = new GF2Polynomial[mDegree - 1];
         int i, j;
         squaringMatrix = new GF2Polynomial[mDegree];
         for (i = 0; i < squaringMatrix.length; i++)
         {
             squaringMatrix[i] = new GF2Polynomial(mDegree, "ZERO");
         }

         for (i = 0; i < mDegree - 1; i++)
         {
             d[i] = new GF2Polynomial(1, "ONE").shiftLeft(mDegree + i)
                 .remainder(fieldPolynomial);
         }
         for (i = 1; i <= Math.abs(mDegree >> 1); i++)
         {
             for (j = 1; j <= mDegree; j++)
             {
                 if (d[mDegree - (i << 1)].testBit(mDegree - j))
                 {
                     squaringMatrix[j - 1].setBit(mDegree - i);
                 }
             }
         }
         for (i = Math.abs(mDegree >> 1) + 1; i <= mDegree; i++)
         {
             squaringMatrix[(i << 1) - mDegree - 1].setBit(mDegree - i);
         }

     }

     /**
      * Computes the field polynomial. This can take a long time for big degrees.
      */
     protected void computeFieldPolynomial()
     {
         if (testTrinomials())
         {
             return;
         }
         if (testPentanomials())
         {
             return;
         }
         testRandom();
     }

     /**
      * Computes the field polynomial. This can take a long time for big degrees.
      */
     protected void computeFieldPolynomial2()
     {
         if (testTrinomials())
         {
             return;
         }
         if (testPentanomials())
         {
             return;
         }
         testRandom();
     }

     /**
      * Tests all trinomials of degree (n+1) until a irreducible is found and
      * stores the result in <i>field polynomial</i>. Returns false if no
      * irreducible trinomial exists in GF(2^n). This can take very long for huge
      * degrees.
      *
      * @return true if an irreducible trinomial is found
      */
     private boolean testTrinomials()
     {
         int i, l;
         boolean done = false;
         l = 0;

         fieldPolynomial = new GF2Polynomial(mDegree + 1);
         fieldPolynomial.setBit(0);
         fieldPolynomial.setBit(mDegree);
         for (i = 1; (i < mDegree) && !done; i++)
         {
             fieldPolynomial.setBit(i);
             done = fieldPolynomial.isIrreducible();
             l++;
             if (done)
             {
                 isTrinomial = true;
                 tc = i;
                 return done;
             }
             fieldPolynomial.resetBit(i);
             done = fieldPolynomial.isIrreducible();
         }

         return done;
     }

     /**
      * Tests all pentanomials of degree (n+1) until a irreducible is found and
      * stores the result in <i>field polynomial</i>. Returns false if no
      * irreducible pentanomial exists in GF(2^n). This can take very long for
      * huge degrees.
      *
      * @return true if an irreducible pentanomial is found
      */
     private boolean testPentanomials()
     {
         int i, j, k, l;
         boolean done = false;
         l = 0;

         fieldPolynomial = new GF2Polynomial(mDegree + 1);
         fieldPolynomial.setBit(0);
         fieldPolynomial.setBit(mDegree);
         for (i = 1; (i <= (mDegree - 3)) && !done; i++)
         {
             fieldPolynomial.setBit(i);
             for (j = i + 1; (j <= (mDegree - 2)) && !done; j++)
             {
                 fieldPolynomial.setBit(j);
                 for (k = j + 1; (k <= (mDegree - 1)) && !done; k++)
                 {
                     fieldPolynomial.setBit(k);
                     if (((mDegree & 1) != 0) | ((i & 1) != 0) | ((j & 1) != 0)
                         | ((k & 1) != 0))
                     {
                         done = fieldPolynomial.isIrreducible();
                         l++;
                         if (done)
                         {
                             isPentanomial = true;
                             pc[0] = i;
                             pc[1] = j;
                             pc[2] = k;
                             return done;
                         }
                     }
                     fieldPolynomial.resetBit(k);
                 }
                 fieldPolynomial.resetBit(j);
             }
             fieldPolynomial.resetBit(i);
         }

         return done;
     }

     /**
      * Tests random polynomials of degree (n+1) until an irreducible is found
      * and stores the result in <i>field polynomial</i>. This can take very
      * long for huge degrees.
      *
      * @return true
      */
     private boolean testRandom()
     {
         int l;
         boolean done = false;

         fieldPolynomial = new GF2Polynomial(mDegree + 1);
         l = 0;
         while (!done)
         {
             l++;
             fieldPolynomial.randomize();
             fieldPolynomial.setBit(mDegree);
             fieldPolynomial.setBit(0);
             if (fieldPolynomial.isIrreducible())
             {
                 done = true;
                 return done;
             }
         }

         return done;
     }

 }
	package org.bouncycastle.pqc.math.linearalgebra;


	import java.security.SecureRandom;
	import java.util.Vector;


	/**
	* This class implements the abstract class <tt>GF2nField</tt> for polynomial
	* representation. It computes the field polynomial and the squaring matrix.
	* GF2nField is used by GF2nPolynomialElement which implements the elements of
	* this field.
	*
	* @see GF2nField
	* @see GF2nPolynomialElement
	*/
	public class GF2nPolynomialField
	extends GF2nField
	{

	/**
	* Matrix used for fast squaring
	*/
	GF2Polynomial[] squaringMatrix;

	// field polynomial is a trinomial
	private boolean isTrinomial = false;

	// field polynomial is a pentanomial
	private boolean isPentanomial = false;

	// middle coefficient of the field polynomial in case it is a trinomial
	private int tc;

	// middle 3 coefficients of the field polynomial in case it is a pentanomial
	private int[] pc = new int[3];

	/**
	* constructs an instance of the finite field with 2<sup>deg</sup>
	* elements and characteristic 2.
	*
	* @param deg the extention degree of this field
	* @param random source of randomness for generating new polynomials.
	*/
	public GF2nPolynomialField(int deg, SecureRandom random)
	{
	super(random);

	if (deg < 3)
	{
	throw new IllegalArgumentException("k must be at least 3");
	}
	mDegree = deg;
	computeFieldPolynomial();
	computeSquaringMatrix();
	fields = new Vector();
	matrices = new Vector();
	}

	/**
	* constructs an instance of the finite field with 2<sup>deg</sup>
	* elements and characteristic 2.
	*
	* @param deg the degree of this field
	* @param random source of randomness for generating new polynomials.
	* @param file true if you want to read the field polynomial from the
	* file false if you want to use a random fielpolynomial
	* (this can take very long for huge degrees)
	*/
	public GF2nPolynomialField(int deg, SecureRandom random, boolean file)
	{
	super(random);

	if (deg < 3)
	{
	throw new IllegalArgumentException("k must be at least 3");
	}
	mDegree = deg;
	if (file)
	{
	computeFieldPolynomial();
	}
	else
	{
	computeFieldPolynomial2();
	}
	computeSquaringMatrix();
	fields = new Vector();
	matrices = new Vector();
	}

	/**
	* Creates a new GF2nField of degree <i>i</i> and uses the given
	* <i>polynomial</i> as field polynomial. The <i>polynomial</i> is checked
	* whether it is irreducible. This can take some time if <i>i</i> is huge!
	*
	* @param deg degree of the GF2nField
	* @param random source of randomness for generating new polynomials.
	* @param polynomial the field polynomial to use
	*/
	public GF2nPolynomialField(int deg, SecureRandom random, GF2Polynomial polynomial)
	throws RuntimeException
	{
	super(random);

	if (deg < 3)
	{
	throw new IllegalArgumentException("degree must be at least 3");
	}
	if (polynomial.getLength() != deg + 1)
	{
	throw new RuntimeException();
	}
	if (!polynomial.isIrreducible())
	{
	throw new RuntimeException();
	}
	mDegree = deg;
	// fieldPolynomial = new Bitstring(polynomial);
	fieldPolynomial = polynomial;
	computeSquaringMatrix();
	int k = 2; // check if the polynomial is a trinomial or pentanomial
	for (int j = 1; j < fieldPolynomial.getLength() - 1; j++)
	{
	if (fieldPolynomial.testBit(j))
	{
	k++;
	if (k == 3)
	{
	tc = j;
	}
	if (k <= 5)
	{
	pc[k - 3] = j;
	}
	}
	}
	if (k == 3)
	{
	isTrinomial = true;
	}
	if (k == 5)
	{
	isPentanomial = true;
	}
	fields = new Vector();
	matrices = new Vector();
	}

	/**
	* Returns true if the field polynomial is a trinomial. The coefficient can
	* be retrieved using getTc().
	*
	* @return true if the field polynomial is a trinomial
	*/
	public boolean isTrinomial()
	{
	return isTrinomial;
	}

	/**
	* Returns true if the field polynomial is a pentanomial. The coefficients
	* can be retrieved using getPc().
	*
	* @return true if the field polynomial is a pentanomial
	*/
	public boolean isPentanomial()
	{
	return isPentanomial;
	}

	/**
	* Returns the degree of the middle coefficient of the used field trinomial
	* (x^n + x^(getTc()) + 1).
	*
	* @return the middle coefficient of the used field trinomial
	*/
	public int getTc()
	throws RuntimeException
	{
	if (!isTrinomial)
	{
	throw new RuntimeException();
	}
	return tc;
	}

	/**
	* Returns the degree of the middle coefficients of the used field
	* pentanomial (x^n + x^(getPc()[2]) + x^(getPc()[1]) + x^(getPc()[0]) + 1).
	*
	* @return the middle coefficients of the used field pentanomial
	*/
	public int[] getPc()
	throws RuntimeException
	{
	if (!isPentanomial)
	{
	throw new RuntimeException();
	}
	int[] result = new int[3];
	System.arraycopy(pc, 0, result, 0, 3);
	return result;
	}

	/**
	* Return row vector i of the squaring matrix.
	*
	* @param i the index of the row vector to return
	* @return a copy of squaringMatrix[i]
	* @see GF2nPolynomialElement#squareMatrix
	*/
	public GF2Polynomial getSquaringVector(int i)
	{
	return new GF2Polynomial(squaringMatrix[i]);
	}

	/**
	* Compute a random root of the given GF2Polynomial.
	*
	* @param polynomial the polynomial
	* @return a random root of <tt>polynomial</tt>
	*/
	protected GF2nElement getRandomRoot(GF2Polynomial polynomial)
	{
	// We are in B1!!!
	GF2nPolynomial c;
	GF2nPolynomial ut;
	GF2nElement u;
	GF2nPolynomial h;
	int hDegree;
	// 1. Set g(t) <- f(t)
	GF2nPolynomial g = new GF2nPolynomial(polynomial, this);
	int gDegree = g.getDegree();
	int i;

	// 2. while deg(g) > 1
	while (gDegree > 1)
	{
	do
	{
	// 2.1 choose random u (element of) GF(2^m)
	u = new GF2nPolynomialElement(this, random);
	ut = new GF2nPolynomial(2, GF2nPolynomialElement.ZERO(this));
	// 2.2 Set c(t) <- ut
	ut.set(1, u);
	c = new GF2nPolynomial(ut);
	// 2.3 For i from 1 to m-1 do
	for (i = 1; i <= mDegree - 1; i++)
	{
	// 2.3.1 c(t) <- (c(t)^2 + ut) mod g(t)
	c = c.multiplyAndReduce(c, g);
	c = c.add(ut);
	}
	// 2.4 set h(t) <- GCD(c(t), g(t))
	h = c.gcd(g);
	// 2.5 if h(t) is constant or deg(g) = deg(h) then go to
	// step 2.1
	hDegree = h.getDegree();
	gDegree = g.getDegree();
	}
	while ((hDegree == 0) \|\| (hDegree == gDegree));
	// 2.6 If 2deg(h) > deg(g) then set g(t) <- g(t)/h(t) ...
	if ((hDegree << 1) > gDegree)
	{
	g = g.quotient(h);
	}
	else
	{
	// ... else g(t) <- h(t)
	g = new GF2nPolynomial(h);
	}
	gDegree = g.getDegree();
	}
	// 3. Output g(0)
	return g.at(0);

	}

	/**
	* Computes the change-of-basis matrix for basis conversion according to
	* 1363. The result is stored in the lists fields and matrices.
	*
	* @param B1 the GF2nField to convert to
	* @see "P1363 A.7.3, p111ff"
	*/
	protected void computeCOBMatrix(GF2nField B1)
	{
	// we are in B0 here!
	if (mDegree != B1.mDegree)
	{
	throw new IllegalArgumentException(
	"GF2nPolynomialField.computeCOBMatrix: B1 has a different "
	+ "degree and thus cannot be coverted to!");
	}
	if (B1 instanceof GF2nONBField)
	{
	// speedup (calculation is done in PolynomialElements instead of
	// ONB)
	B1.computeCOBMatrix(this);
	return;
	}
	int i, j;
	GF2nElement[] gamma;
	GF2nElement u;
	GF2Polynomial[] COBMatrix = new GF2Polynomial[mDegree];
	for (i = 0; i < mDegree; i++)
	{
	COBMatrix[i] = new GF2Polynomial(mDegree);
	}

	// find Random Root
	do
	{
	// u is in representation according to B1
	u = B1.getRandomRoot(fieldPolynomial);
	}
	while (u.isZero());

	// build gamma matrix by multiplying by u
	if (u instanceof GF2nONBElement)
	{
	gamma = new GF2nONBElement[mDegree];
	gamma[mDegree - 1] = GF2nONBElement.ONE((GF2nONBField)B1);
	}
	else
	{
	gamma = new GF2nPolynomialElement[mDegree];
	gamma[mDegree - 1] = GF2nPolynomialElement
	.ONE((GF2nPolynomialField)B1);
	}
	gamma[mDegree - 2] = u;
	for (i = mDegree - 3; i >= 0; i--)
	{
	gamma[i] = (GF2nElement)gamma[i + 1].multiply(u);
	}
	if (B1 instanceof GF2nONBField)
	{
	// convert horizontal gamma matrix by vertical Bitstrings
	for (i = 0; i < mDegree; i++)
	{
	for (j = 0; j < mDegree; j++)
	{
	// TODO remember: ONB treats its Bits in reverse order !!!
	if (gamma[i].testBit(mDegree - j - 1))
	{
	COBMatrix[mDegree - j - 1].setBit(mDegree - i - 1);
	}
	}
	}
	}
	else
	{
	// convert horizontal gamma matrix by vertical Bitstrings
	for (i = 0; i < mDegree; i++)
	{
	for (j = 0; j < mDegree; j++)
	{
	if (gamma[i].testBit(j))
	{
	COBMatrix[mDegree - j - 1].setBit(mDegree - i - 1);
	}
	}
	}
	}

	// store field and matrix for further use
	fields.addElement(B1);
	matrices.addElement(COBMatrix);
	// store field and inverse matrix for further use in B1
	B1.fields.addElement(this);
	B1.matrices.addElement(invertMatrix(COBMatrix));
	}

	/**
	* Computes a new squaring matrix used for fast squaring.
	*
	* @see GF2nPolynomialElement#square
	*/
	private void computeSquaringMatrix()
	{
	GF2Polynomial[] d = new GF2Polynomial[mDegree - 1];
	int i, j;
	squaringMatrix = new GF2Polynomial[mDegree];
	for (i = 0; i < squaringMatrix.length; i++)
	{
	squaringMatrix[i] = new GF2Polynomial(mDegree, "ZERO");
	}

	for (i = 0; i < mDegree - 1; i++)
	{
	d[i] = new GF2Polynomial(1, "ONE").shiftLeft(mDegree + i)
	.remainder(fieldPolynomial);
	}
	for (i = 1; i <= Math.abs(mDegree >> 1); i++)
	{
	for (j = 1; j <= mDegree; j++)
	{
	if (d[mDegree - (i << 1)].testBit(mDegree - j))
	{
	squaringMatrix[j - 1].setBit(mDegree - i);
	}
	}
	}
	for (i = Math.abs(mDegree >> 1) + 1; i <= mDegree; i++)
	{
	squaringMatrix[(i << 1) - mDegree - 1].setBit(mDegree - i);
	}

	}

	/**
	* Computes the field polynomial. This can take a long time for big degrees.
	*/
	protected void computeFieldPolynomial()
	{
	if (testTrinomials())
	{
	return;
	}
	if (testPentanomials())
	{
	return;
	}
	testRandom();
	}

	/**
	* Computes the field polynomial. This can take a long time for big degrees.
	*/
	protected void computeFieldPolynomial2()
	{
	if (testTrinomials())
	{
	return;
	}
	if (testPentanomials())
	{
	return;
	}
	testRandom();
	}

	/**
	* Tests all trinomials of degree (n+1) until a irreducible is found and
	* stores the result in <i>field polynomial</i>. Returns false if no
	* irreducible trinomial exists in GF(2^n). This can take very long for huge
	* degrees.
	*
	* @return true if an irreducible trinomial is found
	*/
	private boolean testTrinomials()
	{
	int i, l;
	boolean done = false;
	l = 0;

	fieldPolynomial = new GF2Polynomial(mDegree + 1);
	fieldPolynomial.setBit(0);
	fieldPolynomial.setBit(mDegree);
	for (i = 1; (i < mDegree) && !done; i++)
	{
	fieldPolynomial.setBit(i);
	done = fieldPolynomial.isIrreducible();
	l++;
	if (done)
	{
	isTrinomial = true;
	tc = i;
	return done;
	}
	fieldPolynomial.resetBit(i);
	done = fieldPolynomial.isIrreducible();
	}

	return done;
	}

	/**
	* Tests all pentanomials of degree (n+1) until a irreducible is found and
	* stores the result in <i>field polynomial</i>. Returns false if no
	* irreducible pentanomial exists in GF(2^n). This can take very long for
	* huge degrees.
	*
	* @return true if an irreducible pentanomial is found
	*/
	private boolean testPentanomials()
	{
	int i, j, k, l;
	boolean done = false;
	l = 0;

	fieldPolynomial = new GF2Polynomial(mDegree + 1);
	fieldPolynomial.setBit(0);
	fieldPolynomial.setBit(mDegree);
	for (i = 1; (i <= (mDegree - 3)) && !done; i++)
	{
	fieldPolynomial.setBit(i);
	for (j = i + 1; (j <= (mDegree - 2)) && !done; j++)
	{
	fieldPolynomial.setBit(j);
	for (k = j + 1; (k <= (mDegree - 1)) && !done; k++)
	{
	fieldPolynomial.setBit(k);
	if (((mDegree & 1) != 0) \| ((i & 1) != 0) \| ((j & 1) != 0)
	\| ((k & 1) != 0))
	{
	done = fieldPolynomial.isIrreducible();
	l++;
	if (done)
	{
	isPentanomial = true;
	pc[0] = i;
	pc[1] = j;
	pc[2] = k;
	return done;
	}
	}
	fieldPolynomial.resetBit(k);
	}
	fieldPolynomial.resetBit(j);
	}
	fieldPolynomial.resetBit(i);
	}

	return done;
	}

	/**
	* Tests random polynomials of degree (n+1) until an irreducible is found
	* and stores the result in <i>field polynomial</i>. This can take very
	* long for huge degrees.
	*
	* @return true
	*/
	private boolean testRandom()
	{
	int l;
	boolean done = false;

	fieldPolynomial = new GF2Polynomial(mDegree + 1);
	l = 0;
	while (!done)
	{
	l++;
	fieldPolynomial.randomize();
	fieldPolynomial.setBit(mDegree);
	fieldPolynomial.setBit(0);
	if (fieldPolynomial.isIrreducible())
	{
	done = true;
	return done;
	}
	}

	return done;
	}

	}