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, 0 insertions, 1266 deletions
diff --git a/crypto/src/pqc/math/linearalgebra/PolynomialGF2mSmallM.cs b/crypto/src/pqc/math/linearalgebra/PolynomialGF2mSmallM.cs deleted file mode 100644 index 9dca71bee..000000000 --- a/crypto/src/pqc/math/linearalgebra/PolynomialGF2mSmallM.cs +++ /dev/null @@ -1,1266 +0,0 @@ -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; - } - } -} |