diff options
Diffstat (limited to 'crypto/src/pqc/math/linearalgebra/PolynomialGF2mSmallM.cs')
| -rw-r--r-- | crypto/src/pqc/math/linearalgebra/PolynomialGF2mSmallM.cs | 1266 |
1 files changed, 1266 insertions, 0 deletions
diff --git a/crypto/src/pqc/math/linearalgebra/PolynomialGF2mSmallM.cs b/crypto/src/pqc/math/linearalgebra/PolynomialGF2mSmallM.cs new file mode 100644 index 000000000..9dca71bee --- /dev/null +++ b/crypto/src/pqc/math/linearalgebra/PolynomialGF2mSmallM.cs @@ -0,0 +1,1266 @@ +using Org.BouncyCastle.Security; +using Org.BouncyCastle.Utilities; +using System; + +namespace Org.BouncyCastle.Pqc.Math.LinearAlgebra +{ + public class PolynomialGF2mSmallM + { + + /** + * the finite field GF(2^m) + */ + private GF2mField field; + + /** + * the degree of this polynomial + */ + private int degree; + + /** + * For the polynomial representation the map f: R->Z*, + * <tt>poly(X) -> [coef_0, coef_1, ...]</tt> is used, where + * <tt>coef_i</tt> is the <tt>i</tt>th coefficient of the polynomial + * represented as int (see {@link GF2mField}). The polynomials are stored + * as int arrays. + */ + private int[] coefficients; + + /* + * some types of polynomials + */ + + /** + * Constant used for polynomial construction (see constructor + * {@link #PolynomialGF2mSmallM(GF2mField, int, char, SecureRandom)}). + */ + public const char RANDOM_IRREDUCIBLE_POLYNOMIAL = 'I'; + + /** + * Construct the zero polynomial over the finite field GF(2^m). + * + * @param field the finite field GF(2^m) + */ + public PolynomialGF2mSmallM(GF2mField field) + { + this.field = field; + degree = -1; + coefficients = new int[1]; + } + + /** + * Construct a polynomial over the finite field GF(2^m). + * + * @param field the finite field GF(2^m) + * @param deg degree of polynomial + * @param typeOfPolynomial type of polynomial + * @param sr PRNG + */ + public PolynomialGF2mSmallM(GF2mField field, int deg, + char typeOfPolynomial, SecureRandom sr) + { + this.field = field; + + switch (typeOfPolynomial) + { + case PolynomialGF2mSmallM.RANDOM_IRREDUCIBLE_POLYNOMIAL: + coefficients = CreateRandomIrreduciblePolynomial(deg, sr); + break; + default: + throw new ArgumentException(" Error: type " + + typeOfPolynomial + + " is not defined for GF2smallmPolynomial"); + } + ComputeDegree(); + } + + /** + * Create an irreducible polynomial with the given degree over the field + * <tt>GF(2^m)</tt>. + * + * @param deg polynomial degree + * @param sr source of randomness + * @return the generated irreducible polynomial + */ + private int[] CreateRandomIrreduciblePolynomial(int deg, SecureRandom sr) + { + int[] resCoeff = new int[deg + 1]; + resCoeff[deg] = 1; + resCoeff[0] = field.GetRandomNonZeroElement(sr); + for (int i = 1; i < deg; i++) + { + resCoeff[i] = field.GetRandomElement(sr); + } + while (!IsIrreducible(resCoeff)) + { + int n = RandUtils.NextInt(sr, deg); + if (n == 0) + { + resCoeff[0] = field.GetRandomNonZeroElement(sr); + } + else + { + resCoeff[n] = field.GetRandomElement(sr); + } + } + return resCoeff; + } + + /** + * Construct a monomial of the given degree over the finite field GF(2^m). + * + * @param field the finite field GF(2^m) + * @param degree the degree of the monomial + */ + public PolynomialGF2mSmallM(GF2mField field, int degree) + { + this.field = field; + this.degree = degree; + coefficients = new int[degree + 1]; + coefficients[degree] = 1; + } + + /** + * Construct the polynomial over the given finite field GF(2^m) from the + * given coefficient vector. + * + * @param field finite field GF2m + * @param coeffs the coefficient vector + */ + public PolynomialGF2mSmallM(GF2mField field, int[] coeffs) + { + this.field = field; + coefficients = NormalForm(coeffs); + ComputeDegree(); + } + + /** + * Create a polynomial over the finite field GF(2^m). + * + * @param field the finite field GF(2^m) + * @param enc byte[] polynomial in byte array form + */ + public PolynomialGF2mSmallM(GF2mField field, byte[] enc) + { + this.field = field; + + // decodes polynomial + int d = 8; + int count = 1; + while (field.GetDegree() > d) + { + count++; + d += 8; + } + + if ((enc.Length % count) != 0) + { + throw new ArgumentException( + " Error: byte array is not encoded polynomial over given finite field GF2m"); + } + + coefficients = new int[enc.Length / count]; + count = 0; + for (int i = 0; i < coefficients.Length; i++) + { + for (int j = 0; j < d; j += 8) + { + coefficients[i] ^= (enc[count++] & 0x000000ff) << j; + } + if (!this.field.IsElementOfThisField(coefficients[i])) + { + throw new ArgumentException( + " Error: byte array is not encoded polynomial over given finite field GF2m"); + } + } + // if HC = 0 for non-zero polynomial, returns error + if ((coefficients.Length != 1) + && (coefficients[coefficients.Length - 1] == 0)) + { + throw new ArgumentException( + " Error: byte array is not encoded polynomial over given finite field GF2m"); + } + ComputeDegree(); + } + + /** + * Copy constructor. + * + * @param other another {@link PolynomialGF2mSmallM} + */ + public PolynomialGF2mSmallM(PolynomialGF2mSmallM other) + { + // field needs not to be cloned since it is immutable + field = other.field; + degree = other.degree; + coefficients = IntUtils.Clone(other.coefficients); + } + + /** + * Create a polynomial over the finite field GF(2^m) out of the given + * coefficient vector. The finite field is also obtained from the + * {@link GF2mVector}. + * + * @param vect the coefficient vector + */ + public PolynomialGF2mSmallM(GF2mVector vect) + { + new PolynomialGF2mSmallM(vect.GetField(), vect.GetIntArrayForm()); + } + + /* + * ------------------------ + */ + + /** + * Return the degree of this polynomial + * + * @return int degree of this polynomial if this is zero polynomial return + * -1 + */ + public int GetDegree() + { + int d = coefficients.Length - 1; + if (coefficients[d] == 0) + { + return -1; + } + return d; + } + + /** + * @return the head coefficient of this polynomial + */ + public int GetHeadCoefficient() + { + if (degree == -1) + { + return 0; + } + return coefficients[degree]; + } + + /** + * Return the head coefficient of a polynomial. + * + * @param a the polynomial + * @return the head coefficient of <tt>a</tt> + */ + private static int HeadCoefficient(int[] a) + { + int degree = ComputeDegree(a); + if (degree == -1) + { + return 0; + } + return a[degree]; + } + + /** + * Return the coefficient with the given index. + * + * @param index the index + * @return the coefficient with the given index + */ + public int GetCoefficient(int index) + { + if ((index < 0) || (index > degree)) + { + return 0; + } + return coefficients[index]; + } + + /** + * Returns encoded polynomial, i.e., this polynomial in byte array form + * + * @return the encoded polynomial + */ + public byte[] GetEncoded() + { + int d = 8; + int count = 1; + while (field.GetDegree() > d) + { + count++; + d += 8; + } + + byte[] res = new byte[coefficients.Length * count]; + count = 0; + for (int i = 0; i < coefficients.Length; i++) + { + for (int j = 0; j < d; j += 8) + { + res[count++] = (byte)(Utils.UnsignedRightBitShiftInt(coefficients[i], j)); + } + } + + return res; + } + + /** + * Evaluate this polynomial <tt>p</tt> at a value <tt>e</tt> (in + * <tt>GF(2^m)</tt>) with the Horner scheme. + * + * @param e the element of the finite field GF(2^m) + * @return <tt>this(e)</tt> + */ + public int evaluateAt(int e) + { + int result = coefficients[degree]; + for (int i = degree - 1; i >= 0; i--) + { + result = field.Mult(result, e) ^ coefficients[i]; + } + return result; + } + + /** + * Compute the sum of this polynomial and the given polynomial. + * + * @param addend the addend + * @return <tt>this + a</tt> (newly created) + */ + public PolynomialGF2mSmallM add(PolynomialGF2mSmallM addend) + { + int[] resultCoeff = Add(coefficients, addend.coefficients); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Add the given polynomial to this polynomial (overwrite this). + * + * @param addend the addend + */ + public void AddToThis(PolynomialGF2mSmallM addend) + { + coefficients = Add(coefficients, addend.coefficients); + ComputeDegree(); + } + + /** + * Compute the sum of two polynomials a and b over the finite field + * <tt>GF(2^m)</tt>. + * + * @param a the first polynomial + * @param b the second polynomial + * @return a + b + */ + private int[] Add(int[] a, int[] b) + { + int[] result, addend; + if (a.Length < b.Length) + { + result = new int[b.Length]; + Array.Copy(b, 0, result, 0, b.Length); + addend = a; + } + else + { + result = new int[a.Length]; + Array.Copy(a, 0, result, 0, a.Length); + addend = b; + } + + for (int i = addend.Length - 1; i >= 0; i--) + { + result[i] = field.add(result[i], addend[i]); + } + + return result; + } + + /** + * Compute the sum of this polynomial and the monomial of the given degree. + * + * @param degree the degree of the monomial + * @return <tt>this + X^k</tt> + */ + public PolynomialGF2mSmallM AddMonomial(int degree) + { + int[] monomial = new int[degree + 1]; + monomial[degree] = 1; + int[] resultCoeff = Add(coefficients, monomial); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Compute the product of this polynomial with an element from GF(2^m). + * + * @param element an element of the finite field GF(2^m) + * @return <tt>this * element</tt> (newly created) + * @throws ArithmeticException if <tt>element</tt> is not an element of the finite + * field this polynomial is defined over. + */ + public PolynomialGF2mSmallM MultWithElement(int element) + { + if (!field.IsElementOfThisField(element)) + { + throw new ArithmeticException( + "Not an element of the finite field this polynomial is defined over."); + } + int[] resultCoeff = MultWithElement(coefficients, element); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Multiply this polynomial with an element from GF(2^m). + * + * @param element an element of the finite field GF(2^m) + * @throws ArithmeticException if <tt>element</tt> is not an element of the finite + * field this polynomial is defined over. + */ + public void MultThisWithElement(int element) + { + if (!field.IsElementOfThisField(element)) + { + throw new ArithmeticException( + "Not an element of the finite field this polynomial is defined over."); + } + coefficients = MultWithElement(coefficients, element); + ComputeDegree(); + } + + /** + * Compute the product of a polynomial a with an element from the finite + * field <tt>GF(2^m)</tt>. + * + * @param a the polynomial + * @param element an element of the finite field GF(2^m) + * @return <tt>a * element</tt> + */ + private int[] MultWithElement(int[] a, int element) + { + int degree = ComputeDegree(a); + if (degree == -1 || element == 0) + { + return new int[1]; + } + + if (element == 1) + { + return IntUtils.Clone(a); + } + + int[] result = new int[degree + 1]; + for (int i = degree; i >= 0; i--) + { + result[i] = field.Mult(a[i], element); + } + + return result; + } + + /** + * Compute the product of this polynomial with a monomial X^k. + * + * @param k the degree of the monomial + * @return <tt>this * X^k</tt> + */ + public PolynomialGF2mSmallM MultWithMonomial(int k) + { + int[] resultCoeff = MultWithMonomial(coefficients, k); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Compute the product of a polynomial with a monomial X^k. + * + * @param a the polynomial + * @param k the degree of the monomial + * @return <tt>a * X^k</tt> + */ + private static int[] MultWithMonomial(int[] a, int k) + { + int d = ComputeDegree(a); + if (d == -1) + { + return new int[1]; + } + int[] result = new int[d + k + 1]; + Array.Copy(a, 0, result, k, d + 1); + return result; + } + + /** + * Divide this polynomial by the given polynomial. + * + * @param f a polynomial + * @return polynomial pair = {q,r} where this = q*f+r and deg(r) < + * deg(f); + */ + public PolynomialGF2mSmallM[] Div(PolynomialGF2mSmallM f) + { + int[][] resultCoeffs = Div(coefficients, f.coefficients); + return new PolynomialGF2mSmallM[]{ + new PolynomialGF2mSmallM(field, resultCoeffs[0]), + new PolynomialGF2mSmallM(field, resultCoeffs[1])}; + } + + /** + * Compute the result of the division of two polynomials over the field + * <tt>GF(2^m)</tt>. + * + * @param a the first polynomial + * @param f the second polynomial + * @return int[][] {q,r}, where a = q*f+r and deg(r) < deg(f); + */ + private int[][] Div(int[] a, int[] f) + { + int df = ComputeDegree(f); + int da = ComputeDegree(a) + 1; + if (df == -1) + { + throw new ArithmeticException("Division by zero."); + } + int[][] result = new int[2][]; + result[0] = new int[1]; + result[1] = new int[da]; + int hc = HeadCoefficient(f); + hc = field.Inverse(hc); + result[0][0] = 0; + Array.Copy(a, 0, result[1], 0, result[1].Length); + while (df <= ComputeDegree(result[1])) + { + int[] q; + int[] coeff = new int[1]; + coeff[0] = field.Mult(HeadCoefficient(result[1]), hc); + q = MultWithElement(f, coeff[0]); + int n = ComputeDegree(result[1]) - df; + q = MultWithMonomial(q, n); + coeff = MultWithMonomial(coeff, n); + result[0] = Add(coeff, result[0]); + result[1] = Add(q, result[1]); + } + return result; + } + + /** + * Return the greatest common divisor of this and a polynomial <i>f</i> + * + * @param f polynomial + * @return GCD(this, f) + */ + public PolynomialGF2mSmallM Gcd(PolynomialGF2mSmallM f) + { + int[] resultCoeff = Gcd(coefficients, f.coefficients); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Return the greatest common divisor of two polynomials over the field + * <tt>GF(2^m)</tt>. + * + * @param f the first polynomial + * @param g the second polynomial + * @return <tt>gcd(f, g)</tt> + */ + private int[] Gcd(int[] f, int[] g) + { + int[] a = f; + int[] b = g; + if (ComputeDegree(a) == -1) + { + return b; + } + while (ComputeDegree(b) != -1) + { + int[] c = Mod(a, b); + a = new int[b.Length]; + Array.Copy(b, 0, a, 0, a.Length); + b = new int[c.Length]; + Array.Copy(c, 0, b, 0, b.Length); + } + int coeff = field.Inverse(HeadCoefficient(a)); + return MultWithElement(a, coeff); + } + + /** + * Compute the product of this polynomial and the given factor using a + * Karatzuba like scheme. + * + * @param factor the polynomial + * @return <tt>this * factor</tt> + */ + public PolynomialGF2mSmallM Multiply(PolynomialGF2mSmallM factor) + { + int[] resultCoeff = Multiply(coefficients, factor.coefficients); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Compute the product of two polynomials over the field <tt>GF(2^m)</tt> + * using a Karatzuba like multiplication. + * + * @param a the first polynomial + * @param b the second polynomial + * @return a * b + */ + private int[] Multiply(int[] a, int[] b) + { + int[] mult1, mult2; + if (ComputeDegree(a) < ComputeDegree(b)) + { + mult1 = b; + mult2 = a; + } + else + { + mult1 = a; + mult2 = b; + } + + mult1 = NormalForm(mult1); + mult2 = NormalForm(mult2); + + if (mult2.Length == 1) + { + return MultWithElement(mult1, mult2[0]); + } + + int d1 = mult1.Length; + int d2 = mult2.Length; + int[] result = new int[d1 + d2 - 1]; + + if (d2 != d1) + { + int[] res1 = new int[d2]; + int[] res2 = new int[d1 - d2]; + Array.Copy(mult1, 0, res1, 0, res1.Length); + Array.Copy(mult1, d2, res2, 0, res2.Length); + res1 = Multiply(res1, mult2); + res2 = Multiply(res2, mult2); + res2 = MultWithMonomial(res2, d2); + result = Add(res1, res2); + } + else + { + d2 = Utils.UnsignedRightBitShiftInt(d1 + 1, 1); + int d = d1 - d2; + int[] firstPartMult1 = new int[d2]; + int[] firstPartMult2 = new int[d2]; + int[] secondPartMult1 = new int[d]; + int[] secondPartMult2 = new int[d]; + Array.Copy(mult1, 0, firstPartMult1, 0, + firstPartMult1.Length); + Array.Copy(mult1, d2, secondPartMult1, 0, + secondPartMult1.Length); + Array.Copy(mult2, 0, firstPartMult2, 0, + firstPartMult2.Length); + Array.Copy(mult2, d2, secondPartMult2, 0, + secondPartMult2.Length); + int[] helpPoly1 = Add(firstPartMult1, secondPartMult1); + int[] helpPoly2 = Add(firstPartMult2, secondPartMult2); + int[] res1 = Multiply(firstPartMult1, firstPartMult2); + int[] res2 = Multiply(helpPoly1, helpPoly2); + int[] res3 = Multiply(secondPartMult1, secondPartMult2); + res2 = Add(res2, res1); + res2 = Add(res2, res3); + res3 = MultWithMonomial(res3, d2); + result = Add(res2, res3); + result = MultWithMonomial(result, d2); + result = Add(result, res1); + } + + return result; + } + + /* + * ---------------- PART II ---------------- + * + */ + + /** + * Check a polynomial for irreducibility over the field <tt>GF(2^m)</tt>. + * + * @param a the polynomial to check + * @return true if a is irreducible, false otherwise + */ + private bool IsIrreducible(int[] a) + { + if (a[0] == 0) + { + return false; + } + int d = ComputeDegree(a) >> 1; + int[] u = { 0, 1 }; + int[] Y = { 0, 1 }; + int fieldDegree = field.GetDegree(); + for (int i = 0; i < d; i++) + { + for (int j = fieldDegree - 1; j >= 0; j--) + { + u = ModMultiply(u, u, a); + } + u = NormalForm(u); + int[] g = Gcd(Add(u, Y), a); + if (ComputeDegree(g) != 0) + { + return false; + } + } + return true; + } + + /** + * Reduce this polynomial modulo another polynomial. + * + * @param f the reduction polynomial + * @return <tt>this mod f</tt> + */ + public PolynomialGF2mSmallM Mod(PolynomialGF2mSmallM f) + { + int[] resultCoeff = Mod(coefficients, f.coefficients); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Reduce a polynomial modulo another polynomial. + * + * @param a the polynomial + * @param f the reduction polynomial + * @return <tt>a mod f</tt> + */ + private int[] Mod(int[] a, int[] f) + { + int df = ComputeDegree(f); + if (df == -1) + { + throw new ArithmeticException("Division by zero"); + } + int[] result = new int[a.Length]; + int hc = HeadCoefficient(f); + hc = field.Inverse(hc); + Array.Copy(a, 0, result, 0, result.Length); + while (df <= ComputeDegree(result)) + { + int[] q; + int coeff = field.Mult(HeadCoefficient(result), hc); + q = MultWithMonomial(f, ComputeDegree(result) - df); + q = MultWithElement(q, coeff); + result = Add(q, result); + } + return result; + } + + /** + * Compute the product of this polynomial and another polynomial modulo a + * third polynomial. + * + * @param a another polynomial + * @param b the reduction polynomial + * @return <tt>this * a mod b</tt> + */ + public PolynomialGF2mSmallM ModMultiply(PolynomialGF2mSmallM a, + PolynomialGF2mSmallM b) + { + int[] resultCoeff = ModMultiply(coefficients, a.coefficients, + b.coefficients); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + + + /** + * Square this polynomial using a squaring matrix. + * + * @param matrix the squaring matrix + * @return <tt>this^2</tt> modulo the reduction polynomial implicitly + * given via the squaring matrix + */ + public PolynomialGF2mSmallM ModSquareMatrix(PolynomialGF2mSmallM[] matrix) + { + + int length = matrix.Length; + + int[] resultCoeff = new int[length]; + int[] thisSquare = new int[length]; + + // square each entry of this polynomial + for (int i = 0; i < coefficients.Length; i++) + { + thisSquare[i] = field.Mult(coefficients[i], coefficients[i]); + } + + // do matrix-vector multiplication + for (int i = 0; i < length; i++) + { + // compute scalar product of i-th row and coefficient vector + for (int j = 0; j < length; j++) + { + if (i >= matrix[j].coefficients.Length) + { + continue; + } + int scalarTerm = field.Mult(matrix[j].coefficients[i], + thisSquare[j]); + resultCoeff[i] = field.add(resultCoeff[i], scalarTerm); + } + } + + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Compute the product of two polynomials modulo a third polynomial over the + * finite field <tt>GF(2^m)</tt>. + * + * @param a the first polynomial + * @param b the second polynomial + * @param g the reduction polynomial + * @return <tt>a * b mod g</tt> + */ + private int[] ModMultiply(int[] a, int[] b, int[] g) + { + return Mod(Multiply(a, b), g); + } + + /** + * Compute the square root of this polynomial modulo the given polynomial. + * + * @param a the reduction polynomial + * @return <tt>this^(1/2) mod a</tt> + */ + public PolynomialGF2mSmallM ModSquareRoot(PolynomialGF2mSmallM a) + { + int[] resultCoeff = IntUtils.Clone(coefficients); + int[] help = ModMultiply(resultCoeff, resultCoeff, a.coefficients); + while (!IsEqual(help, coefficients)) + { + resultCoeff = NormalForm(help); + help = ModMultiply(resultCoeff, resultCoeff, a.coefficients); + } + + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Compute the square root of this polynomial using a square root matrix. + * + * @param matrix the matrix for computing square roots in + * <tt>(GF(2^m))^t</tt> the polynomial ring defining the + * square root matrix + * @return <tt>this^(1/2)</tt> modulo the reduction polynomial implicitly + * given via the square root matrix + */ + public PolynomialGF2mSmallM ModSquareRootMatrix( + PolynomialGF2mSmallM[] matrix) + { + + int length = matrix.Length; + + int[] resultCoeff = new int[length]; + + // do matrix multiplication + for (int i = 0; i < length; i++) + { + // compute scalar product of i-th row and j-th column + for (int j = 0; j < length; j++) + { + if (i >= matrix[j].coefficients.Length) + { + continue; + } + if (j < coefficients.Length) + { + int scalarTerm = field.Mult(matrix[j].coefficients[i], + coefficients[j]); + resultCoeff[i] = field.add(resultCoeff[i], scalarTerm); + } + } + } + + // compute the square root of each entry of the result coefficients + for (int i = 0; i < length; i++) + { + resultCoeff[i] = field.SqRoot(resultCoeff[i]); + } + + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Compute the result of the division of this polynomial by another + * polynomial modulo a third polynomial. + * + * @param divisor the divisor + * @param modulus the reduction polynomial + * @return <tt>this * divisor^(-1) mod modulus</tt> + */ + public PolynomialGF2mSmallM ModDiv(PolynomialGF2mSmallM divisor, + PolynomialGF2mSmallM modulus) + { + int[] resultCoeff = ModDiv(coefficients, divisor.coefficients, + modulus.coefficients); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Compute the result of the division of two polynomials modulo a third + * polynomial over the field <tt>GF(2^m)</tt>. + * + * @param a the first polynomial + * @param b the second polynomial + * @param g the reduction polynomial + * @return <tt>a * b^(-1) mod g</tt> + */ + private int[] ModDiv(int[] a, int[] b, int[] g) + { + int[] r0 = NormalForm(g); + int[] r1 = Mod(b, g); + int[] s0 = { 0 }; + int[] s1 = Mod(a, g); + int[] s2; + int[][] q; + while (ComputeDegree(r1) != -1) + { + q = Div(r0, r1); + r0 = NormalForm(r1); + r1 = NormalForm(q[1]); + s2 = Add(s0, ModMultiply(q[0], s1, g)); + s0 = NormalForm(s1); + s1 = NormalForm(s2); + + } + int hc = HeadCoefficient(r0); + s0 = MultWithElement(s0, field.Inverse(hc)); + return s0; + } + + /** + * Compute the inverse of this polynomial modulo the given polynomial. + * + * @param a the reduction polynomial + * @return <tt>this^(-1) mod a</tt> + */ + public PolynomialGF2mSmallM ModInverse(PolynomialGF2mSmallM a) + { + int[] unit = { 1 }; + int[] resultCoeff = ModDiv(unit, coefficients, a.coefficients); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Compute a polynomial pair (a,b) from this polynomial and the given + * polynomial g with the property b*this = a mod g and deg(a)<=deg(g)/2. + * + * @param g the reduction polynomial + * @return PolynomialGF2mSmallM[] {a,b} with b*this = a mod g and deg(a)<= + * deg(g)/2 + */ + public PolynomialGF2mSmallM[] ModPolynomialToFracton(PolynomialGF2mSmallM g) + { + int dg = g.degree >> 1; + int[] a0 = NormalForm(g.coefficients); + int[] a1 = Mod(coefficients, g.coefficients); + int[] b0 = { 0 }; + int[] b1 = { 1 }; + while (ComputeDegree(a1) > dg) + { + int[][] q = Div(a0, a1); + a0 = a1; + a1 = q[1]; + int[] b2 = Add(b0, ModMultiply(q[0], b1, g.coefficients)); + b0 = b1; + b1 = b2; + } + + return new PolynomialGF2mSmallM[]{ + new PolynomialGF2mSmallM(field, a1), + new PolynomialGF2mSmallM(field, b1)}; + } + + /** + * checks if given object is equal to this polynomial. + * <p> + * The method returns false whenever the given object is not polynomial over + * GF(2^m). + * + * @param other object + * @return true or false + */ + public bool equals(Object other) + { + + if (other == null || !(other is PolynomialGF2mSmallM)) + { + return false; + } + + PolynomialGF2mSmallM p = (PolynomialGF2mSmallM)other; + + if ((field.Equals(p.field)) && (degree == p.degree) + && (IsEqual(coefficients, p.coefficients))) + { + return true; + } + + return false; + } + + /** + * Compare two polynomials given as int arrays. + * + * @param a the first polynomial + * @param b the second polynomial + * @return <tt>true</tt> if <tt>a</tt> and <tt>b</tt> represent the + * same polynomials, <tt>false</tt> otherwise + */ + private static bool IsEqual(int[] a, int[] b) + { + int da = ComputeDegree(a); + int db = ComputeDegree(b); + if (da != db) + { + return false; + } + for (int i = 0; i <= da; i++) + { + if (a[i] != b[i]) + { + return false; + } + } + return true; + } + + /** + * @return the hash code of this polynomial + */ + public int HashCode() + { + int hash = field.HashCode(); + for (int j = 0; j < coefficients.Length; j++) + { + hash = hash * 31 + coefficients[j]; + } + return hash; + } + + /** + * Returns a human readable form of the polynomial. + * + * @return a human readable form of the polynomial. + */ + public String toString() + { + String str = " Polynomial over " + field.ToString() + ": \n"; + + for (int i = 0; i < coefficients.Length; i++) + { + str = str + field.ElementToStr(coefficients[i]) + "Y^" + i + "+"; + } + str = str + ";"; + + return str; + } + + /** + * Compute the degree of this polynomial. If this is the zero polynomial, + * the degree is -1. + */ + private void ComputeDegree() + { + for (degree = coefficients.Length - 1; degree >= 0 + && coefficients[degree] == 0; degree--) + { + ; + } + } + + /** + * Compute the degree of a polynomial. + * + * @param a the polynomial + * @return the degree of the polynomial <tt>a</tt>. If <tt>a</tt> is + * the zero polynomial, return -1. + */ + private static int ComputeDegree(int[] a) + { + int degree; + for (degree = a.Length - 1; degree >= 0 && a[degree] == 0; degree--) + { + ; + } + return degree; + } + + /** + * Strip leading zero coefficients from the given polynomial. + * + * @param a the polynomial + * @return the reduced polynomial + */ + private static int[] NormalForm(int[] a) + { + int d = ComputeDegree(a); + + // if a is the zero polynomial + if (d == -1) + { + // return new zero polynomial + return new int[1]; + } + + // if a already is in normal form + if (a.Length == d + 1) + { + // return a clone of a + return IntUtils.Clone(a); + } + + // else, reduce a + int[] result = new int[d + 1]; + Array.Copy(a, 0, result, 0, d + 1); + return result; + } + + /** + * Compute the product of this polynomial and another polynomial modulo a + * third polynomial. + * + * @param a another polynomial + * @param b the reduction polynomial + * @return <tt>this * a mod b</tt> + */ + public PolynomialGF2mSmallM ModKaratsubaMultiplyBigDeg(PolynomialGF2mSmallM a, + PolynomialGF2mSmallM b) + { + int[] resultCoeff = ModKaratsubaMultiplyBigDeg(coefficients, a.coefficients, + b.coefficients); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + /** + * Compute the inverse of this polynomial modulo the given polynomial. + * + * @param a the reduction polynomial + * @return <tt>this^(-1) mod a</tt> + */ + public PolynomialGF2mSmallM ModInverseBigDeg(PolynomialGF2mSmallM a) + { + int[] unit = { 1 }; + int[] resultCoeff = ModDivBigDeg(unit, coefficients, a.coefficients); + return new PolynomialGF2mSmallM(field, resultCoeff); + } + + private int[] ModDivBigDeg(int[] a, int[] b, int[] g) + { + int[] r0 = NormalForm(g); + int[] r1 = Mod(b, g); + int[] s0 = { 0 }; + int[] s1 = Mod(a, g); + int[] s2; + int[][] q; + while (ComputeDegree(r1) != -1) + { + q = Div(r0, r1); + r0 = NormalForm(r1); + r1 = NormalForm(q[1]); + s2 = Add(s0, ModKaratsubaMultiplyBigDeg(q[0], s1, g)); + s0 = NormalForm(s1); + s1 = NormalForm(s2); + } + int hc = HeadCoefficient(r0); + s0 = MultWithElement(s0, field.Inverse(hc)); + return s0; + } + + /** + * Compute the product of two polynomials modulo a third polynomial over the + * finite field <tt>GF(2^m)</tt>. + * + * @param aa the first polynomial + * @param bb the second polynomial + * @param g the reduction polynomial + * @return <tt>a * b mod g</tt> + */ + private int[] ModKaratsubaMultiplyBigDeg(int[] aa, int[] bb, int[] g) + { + int[] a, b; + if (aa.Length >= bb.Length) + { + a = Arrays.Clone(aa); + b = Arrays.Clone(bb); + } + else + { + a = Arrays.Clone(bb); + b = Arrays.Clone(aa); + } + + int n = a.Length; + int m = b.Length; + + int[] D = new int[(n + m) / 2]; + int[] S = new int[n + m - 1]; + int[] T = new int[n + m - 1]; + int[] C = new int[n + m - 1]; + + for (int i = 0; i < m; i++) + { + D[i] = a[i] * b[i]; + } + + for (int i = 1; i < n + m - 2; i++) + { + for (int p = 0; p < System.Math.Min(m, i); p++) + { + int q = i - p; + if (p >= q) + { + break; + } + + int ap = a[p]; + int aq = 0; + + if (q < a.Length) + { + aq = a[q]; + } + + int bp = b[p]; + int dp = D[p]; + + if (q < m && p < m) + { + int bq = b[q]; + int dq = D[q]; + + S[i] = S[i] + (ap + aq) * (bp + bq); + T[i] = T[i] + dp + dq; + } + else if (q >= m && q < n) + { + S[i] = S[i] + ((ap + aq) * bp); + T[i] = T[i] + dp; + } + } + } + + for (int i = 0; i < n + m - 1; i++) + { + if (i == 0) + { + C[i] = D[i] % 2; + } + else if (i == n + m - 2) + { + C[i] = (a[a.Length - 1] * b[b.Length - 1]) % 2; + } + else if (i % 2 == 1) + { + C[i] = (S[i] - T[i]) % 2; + } + else + { + C[i] = (S[i] - T[i] + D[i / 2]) % 2; + } + } + int[] res = Mod(C, g); + return res; + } + } +} |