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

 package org.bouncycastle.pqc.math.linearalgebra;

 import java.security.SecureRandom;

 import org.bouncycastle.crypto.CryptoServicesRegistrar;

 /**
  * This class describes operations with elements from the finite field F =
  * GF(2^m). ( GF(2^m)= GF(2)[A] where A is a root of irreducible polynomial with
  * degree m, each field element B has a polynomial basis representation, i.e. it
  * is represented by a different binary polynomial of degree less than m, B =
  * poly(A) ) All operations are defined only for field with 1&lt; m &lt;32. For the
  * representation of field elements the map f: F-&gt;Z, poly(A)-&gt;poly(2) is used,
  * where integers have the binary representation. For example: A^7+A^3+A+1 -&gt;
  * (00...0010001011)=139 Also for elements type Integer is used.
  *
  * @see PolynomialRingGF2
  */
 public class GF2mField
 {

     /*
       * degree - degree of the field polynomial - the field polynomial ring -
       * polynomial ring over the finite field GF(2)
       */

     private int degree = 0;

     private int polynomial;

     /**
      * create a finite field GF(2^m)
      *
      * @param degree the degree of the field
      */
     public GF2mField(int degree)
     {
         if (degree >= 32)
         {
             throw new IllegalArgumentException(
                 " Error: the degree of field is too large ");
         }
         if (degree < 1)
         {
             throw new IllegalArgumentException(
                 " Error: the degree of field is non-positive ");
         }
         this.degree = degree;
         polynomial = PolynomialRingGF2.getIrreduciblePolynomial(degree);
     }

     /**
      * create a finite field GF(2^m) with the fixed field polynomial
      *
      * @param degree the degree of the field
      * @param poly   the field polynomial
      */
     public GF2mField(int degree, int poly)
     {
         if (degree != PolynomialRingGF2.degree(poly))
         {
             throw new IllegalArgumentException(
                 " Error: the degree is not correct");
         }
         if (!PolynomialRingGF2.isIrreducible(poly))
         {
             throw new IllegalArgumentException(
                 " Error: given polynomial is reducible");
         }
         this.degree = degree;
         polynomial = poly;

     }

     public GF2mField(byte[] enc)
     {
         if (enc.length != 4)
         {
             throw new IllegalArgumentException(
                 "byte array is not an encoded finite field");
         }
         polynomial = LittleEndianConversions.OS2IP(enc);
         if (!PolynomialRingGF2.isIrreducible(polynomial))
         {
             throw new IllegalArgumentException(
                 "byte array is not an encoded finite field");
         }

         degree = PolynomialRingGF2.degree(polynomial);
     }

     public GF2mField(GF2mField field)
     {
         degree = field.degree;
         polynomial = field.polynomial;
     }

     /**
      * return degree of the field
      *
      * @return degree of the field
      */
     public int getDegree()
     {
         return degree;
     }

     /**
      * return the field polynomial
      *
      * @return the field polynomial
      */
     public int getPolynomial()
     {
         return polynomial;
     }

     /**
      * return the encoded form of this field
      *
      * @return the field in byte array form
      */
     public byte[] getEncoded()
     {
         return LittleEndianConversions.I2OSP(polynomial);
     }

     /**
      * Return sum of two elements
      *
      * @param a
      * @param b
      * @return a+b
      */
     public int add(int a, int b)
     {
         return a ^ b;
     }

     /**
      * Return product of two elements
      *
      * @param a
      * @param b
      * @return a*b
      */
     public int mult(int a, int b)
     {
         return PolynomialRingGF2.modMultiply(a, b, polynomial);
     }

     /**
      * compute exponentiation a^k
      *
      * @param a a field element a
      * @param k k degree
      * @return a^k
      */
     public int exp(int a, int k)
     {
         if (k == 0)
         {
             return 1;
         }
         if (a == 0)
         {
             return 0;
         }
         if (a == 1)
         {
             return 1;
         }
         int result = 1;
         if (k < 0)
         {
             a = inverse(a);
             k = -k;
         }
         while (k != 0)
         {
             if ((k & 1) == 1)
             {
                 result = mult(result, a);
             }
             a = mult(a, a);
             k >>>= 1;
         }
         return result;
     }

     /**
      * compute the multiplicative inverse of a
      *
      * @param a a field element a
      * @return a<sup>-1</sup>
      */
     public int inverse(int a)
     {
         int d = (1 << degree) - 2;

         return exp(a, d);
     }

     /**
      * compute the square root of an integer
      *
      * @param a a field element a
      * @return a<sup>1/2</sup>
      */
     public int sqRoot(int a)
     {
         for (int i = 1; i < degree; i++)
         {
             a = mult(a, a);
         }
         return a;
     }

     /**
      * create a random field element using PRNG sr
      *
      * @param sr SecureRandom
      * @return a random element
      */
     public int getRandomElement(SecureRandom sr)
     {
         int result = RandUtils.nextInt(sr, 1 << degree);
         return result;
     }

     /**
      * create a random non-zero field element
      *
      * @return a random element
      */
     public int getRandomNonZeroElement()
     {
         return getRandomNonZeroElement(CryptoServicesRegistrar.getSecureRandom());
     }

     /**
      * create a random non-zero field element using PRNG sr
      *
      * @param sr SecureRandom
      * @return a random non-zero element
      */
     public int getRandomNonZeroElement(SecureRandom sr)
     {
         int controltime = 1 << 20;
         int count = 0;
         int result = RandUtils.nextInt(sr, 1 << degree);
         while ((result == 0) && (count < controltime))
         {
             result = RandUtils.nextInt(sr, 1 << degree);
             count++;
         }
         if (count == controltime)
         {
             result = 1;
         }
         return result;
     }

     /**
      * @return true if e is encoded element of this field and false otherwise
      */
     public boolean isElementOfThisField(int e)
     {
         // e is encoded element of this field iff 0<= e < |2^m|
         if (degree == 31)
         {
             return e >= 0;
         }
         return e >= 0 && e < (1 << degree);
     }

     /*
       * help method for visual control
       */
     public String elementToStr(int a)
     {
         String s = "";
         for (int i = 0; i < degree; i++)
         {
             if (((byte)a & 0x01) == 0)
             {
                 s = "0" + s;
             }
             else
             {
                 s = "1" + s;
             }
             a >>>= 1;
         }
         return s;
     }

     /**
      * checks if given object is equal to this field.
      * <p>
      * The method returns false whenever the given object is not GF2m.
      *
      * @param other object
      * @return true or false
      */
     public boolean equals(Object other)
     {
         if ((other == null) || !(other instanceof GF2mField))
         {
             return false;
         }

         GF2mField otherField = (GF2mField)other;

         if ((degree == otherField.degree)
             && (polynomial == otherField.polynomial))
         {
             return true;
         }

         return false;
     }

     public int hashCode()
     {
         return polynomial;
     }

     /**
      * Returns a human readable form of this field.
      *
      * @return a human readable form of this field.
      */
     public String toString()
     {
         String str = "Finite Field GF(2^" + degree + ") = " + "GF(2)[X]/<"
             + polyToString(polynomial) + "> ";
         return str;
     }

     private static String polyToString(int p)
     {
         String str = "";
         if (p == 0)
         {
             str = "0";
         }
         else
         {
             byte b = (byte)(p & 0x01);
             if (b == 1)
             {
                 str = "1";
             }
             p >>>= 1;
             int i = 1;
             while (p != 0)
             {
                 b = (byte)(p & 0x01);
                 if (b == 1)
                 {
                     str = str + "+x^" + i;
                 }
                 p >>>= 1;
                 i++;
             }
         }
         return str;
     }

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

	import java.security.SecureRandom;

	import org.bouncycastle.crypto.CryptoServicesRegistrar;

	/**
	* This class describes operations with elements from the finite field F =
	* GF(2^m). ( GF(2^m)= GF(2)[A] where A is a root of irreducible polynomial with
	* degree m, each field element B has a polynomial basis representation, i.e. it
	* is represented by a different binary polynomial of degree less than m, B =
	* poly(A) ) All operations are defined only for field with 1< m <32. For the
	* representation of field elements the map f: F->Z, poly(A)->poly(2) is used,
	* where integers have the binary representation. For example: A^7+A^3+A+1 ->
	* (00...0010001011)=139 Also for elements type Integer is used.
	*
	* @see PolynomialRingGF2
	*/
	public class GF2mField
	{

	/*
	* degree - degree of the field polynomial - the field polynomial ring -
	* polynomial ring over the finite field GF(2)
	*/

	private int degree = 0;

	private int polynomial;

	/**
	* create a finite field GF(2^m)
	*
	* @param degree the degree of the field
	*/
	public GF2mField(int degree)
	{
	if (degree >= 32)
	{
	throw new IllegalArgumentException(
	" Error: the degree of field is too large ");
	}
	if (degree < 1)
	{
	throw new IllegalArgumentException(
	" Error: the degree of field is non-positive ");
	}
	this.degree = degree;
	polynomial = PolynomialRingGF2.getIrreduciblePolynomial(degree);
	}

	/**
	* create a finite field GF(2^m) with the fixed field polynomial
	*
	* @param degree the degree of the field
	* @param poly the field polynomial
	*/
	public GF2mField(int degree, int poly)
	{
	if (degree != PolynomialRingGF2.degree(poly))
	{
	throw new IllegalArgumentException(
	" Error: the degree is not correct");
	}
	if (!PolynomialRingGF2.isIrreducible(poly))
	{
	throw new IllegalArgumentException(
	" Error: given polynomial is reducible");
	}
	this.degree = degree;
	polynomial = poly;

	}

	public GF2mField(byte[] enc)
	{
	if (enc.length != 4)
	{
	throw new IllegalArgumentException(
	"byte array is not an encoded finite field");
	}
	polynomial = LittleEndianConversions.OS2IP(enc);
	if (!PolynomialRingGF2.isIrreducible(polynomial))
	{
	throw new IllegalArgumentException(
	"byte array is not an encoded finite field");
	}

	degree = PolynomialRingGF2.degree(polynomial);
	}

	public GF2mField(GF2mField field)
	{
	degree = field.degree;
	polynomial = field.polynomial;
	}

	/**
	* return degree of the field
	*
	* @return degree of the field
	*/
	public int getDegree()
	{
	return degree;
	}

	/**
	* return the field polynomial
	*
	* @return the field polynomial
	*/
	public int getPolynomial()
	{
	return polynomial;
	}

	/**
	* return the encoded form of this field
	*
	* @return the field in byte array form
	*/
	public byte[] getEncoded()
	{
	return LittleEndianConversions.I2OSP(polynomial);
	}

	/**
	* Return sum of two elements
	*
	* @param a
	* @param b
	* @return a+b
	*/
	public int add(int a, int b)
	{
	return a ^ b;
	}

	/**
	* Return product of two elements
	*
	* @param a
	* @param b
	* @return a*b
	*/
	public int mult(int a, int b)
	{
	return PolynomialRingGF2.modMultiply(a, b, polynomial);
	}

	/**
	* compute exponentiation a^k
	*
	* @param a a field element a
	* @param k k degree
	* @return a^k
	*/
	public int exp(int a, int k)
	{
	if (k == 0)
	{
	return 1;
	}
	if (a == 0)
	{
	return 0;
	}
	if (a == 1)
	{
	return 1;
	}
	int result = 1;
	if (k < 0)
	{
	a = inverse(a);
	k = -k;
	}
	while (k != 0)
	{
	if ((k & 1) == 1)
	{
	result = mult(result, a);
	}
	a = mult(a, a);
	k >>>= 1;
	}
	return result;
	}

	/**
	* compute the multiplicative inverse of a
	*
	* @param a a field element a
	* @return a<sup>-1</sup>
	*/
	public int inverse(int a)
	{
	int d = (1 << degree) - 2;

	return exp(a, d);
	}

	/**
	* compute the square root of an integer
	*
	* @param a a field element a
	* @return a<sup>1/2</sup>
	*/
	public int sqRoot(int a)
	{
	for (int i = 1; i < degree; i++)
	{
	a = mult(a, a);
	}
	return a;
	}

	/**
	* create a random field element using PRNG sr
	*
	* @param sr SecureRandom
	* @return a random element
	*/
	public int getRandomElement(SecureRandom sr)
	{
	int result = RandUtils.nextInt(sr, 1 << degree);
	return result;
	}

	/**
	* create a random non-zero field element
	*
	* @return a random element
	*/
	public int getRandomNonZeroElement()
	{
	return getRandomNonZeroElement(CryptoServicesRegistrar.getSecureRandom());
	}

	/**
	* create a random non-zero field element using PRNG sr
	*
	* @param sr SecureRandom
	* @return a random non-zero element
	*/
	public int getRandomNonZeroElement(SecureRandom sr)
	{
	int controltime = 1 << 20;
	int count = 0;
	int result = RandUtils.nextInt(sr, 1 << degree);
	while ((result == 0) && (count < controltime))
	{
	result = RandUtils.nextInt(sr, 1 << degree);
	count++;
	}
	if (count == controltime)
	{
	result = 1;
	}
	return result;
	}

	/**
	* @return true if e is encoded element of this field and false otherwise
	*/
	public boolean isElementOfThisField(int e)
	{
	// e is encoded element of this field iff 0<= e < \|2^m\|
	if (degree == 31)
	{
	return e >= 0;
	}
	return e >= 0 && e < (1 << degree);
	}

	/*
	* help method for visual control
	*/
	public String elementToStr(int a)
	{
	String s = "";
	for (int i = 0; i < degree; i++)
	{
	if (((byte)a & 0x01) == 0)
	{
	s = "0" + s;
	}
	else
	{
	s = "1" + s;
	}
	a >>>= 1;
	}
	return s;
	}

	/**
	* checks if given object is equal to this field.
	* <p>
	* The method returns false whenever the given object is not GF2m.
	*
	* @param other object
	* @return true or false
	*/
	public boolean equals(Object other)
	{
	if ((other == null) \|\| !(other instanceof GF2mField))
	{
	return false;
	}

	GF2mField otherField = (GF2mField)other;

	if ((degree == otherField.degree)
	&& (polynomial == otherField.polynomial))
	{
	return true;
	}

	return false;
	}

	public int hashCode()
	{
	return polynomial;
	}

	/**
	* Returns a human readable form of this field.
	*
	* @return a human readable form of this field.
	*/
	public String toString()
	{
	String str = "Finite Field GF(2^" + degree + ") = " + "GF(2)[X]/<"
	+ polyToString(polynomial) + "> ";
	return str;
	}

	private static String polyToString(int p)
	{
	String str = "";
	if (p == 0)
	{
	str = "0";
	}
	else
	{
	byte b = (byte)(p & 0x01);
	if (b == 1)
	{
	str = "1";
	}
	p >>>= 1;
	int i = 1;
	while (p != 0)
	{
	b = (byte)(p & 0x01);
	if (b == 1)
	{
	str = str + "+x^" + i;
	}
	p >>>= 1;
	i++;
	}
	}
	return str;
	}

	}