diff options
Diffstat (limited to 'core/src/main/java/org/bouncycastle/pqc/math/linearalgebra/PolynomialGF2mSmallM.java')
| -rw-r--r-- | core/src/main/java/org/bouncycastle/pqc/math/linearalgebra/PolynomialGF2mSmallM.java | 1124 |
1 files changed, 0 insertions, 1124 deletions
diff --git a/core/src/main/java/org/bouncycastle/pqc/math/linearalgebra/PolynomialGF2mSmallM.java b/core/src/main/java/org/bouncycastle/pqc/math/linearalgebra/PolynomialGF2mSmallM.java deleted file mode 100644 index 866b6f7c..00000000 --- a/core/src/main/java/org/bouncycastle/pqc/math/linearalgebra/PolynomialGF2mSmallM.java +++ /dev/null @@ -1,1124 +0,0 @@ -package org.bouncycastle.pqc.math.linearalgebra; - -import java.security.SecureRandom; - -/** - * This class describes operations with polynomials from the ring R = - * GF(2^m)[X], where 2 <= m <=31. - * - * @see GF2mField - * @see PolynomialRingGF2m - */ -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 static final 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 IllegalArgumentException(" 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 IllegalArgumentException( - " 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 IllegalArgumentException( - " 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 IllegalArgumentException( - " 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) - { - this(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)(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]; - System.arraycopy(b, 0, result, 0, b.length); - addend = a; - } - else - { - result = new int[a.length]; - System.arraycopy(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]; - System.arraycopy(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; - System.arraycopy(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]; - System.arraycopy(b, 0, a, 0, a.length); - b = new int[c.length]; - System.arraycopy(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]; - System.arraycopy(mult1, 0, res1, 0, res1.length); - System.arraycopy(mult1, d2, res2, 0, res2.length); - res1 = multiply(res1, mult2); - res2 = multiply(res2, mult2); - res2 = multWithMonomial(res2, d2); - result = add(res1, res2); - } - else - { - d2 = (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]; - System - .arraycopy(mult1, 0, firstPartMult1, 0, - firstPartMult1.length); - System.arraycopy(mult1, d2, secondPartMult1, 0, - secondPartMult1.length); - System - .arraycopy(mult2, 0, firstPartMult2, 0, - firstPartMult2.length); - System.arraycopy(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 boolean isIrreducible(int[] a) - { - if (a[0] == 0) - { - return false; - } - int d = computeDegree(a) >> 1; - int[] u = {0, 1}; - final 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); - System.arraycopy(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 boolean equals(Object other) - { - - if (other == null || !(other instanceof 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 boolean 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]; - System.arraycopy(a, 0, result, 0, d + 1); - return result; - } - -} |