diff options
Diffstat (limited to 'core/src/main/java/org/spongycastle/pqc/math/linearalgebra/PolynomialGF2mSmallM.java')
| -rw-r--r-- | core/src/main/java/org/spongycastle/pqc/math/linearalgebra/PolynomialGF2mSmallM.java | 1124 |
1 files changed, 1124 insertions, 0 deletions
diff --git a/core/src/main/java/org/spongycastle/pqc/math/linearalgebra/PolynomialGF2mSmallM.java b/core/src/main/java/org/spongycastle/pqc/math/linearalgebra/PolynomialGF2mSmallM.java new file mode 100644 index 00000000..6426a4ce --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/math/linearalgebra/PolynomialGF2mSmallM.java @@ -0,0 +1,1124 @@ +package org.spongycastle.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; + } + +} |