diff options
Diffstat (limited to 'core/src/main/java/org/bouncycastle/pqc/math/linearalgebra/GF2nPolynomial.java')
-rw-r--r-- | core/src/main/java/org/bouncycastle/pqc/math/linearalgebra/GF2nPolynomial.java | 587 |
1 files changed, 587 insertions, 0 deletions
diff --git a/core/src/main/java/org/bouncycastle/pqc/math/linearalgebra/GF2nPolynomial.java b/core/src/main/java/org/bouncycastle/pqc/math/linearalgebra/GF2nPolynomial.java new file mode 100644 index 00000000..f122be03 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/math/linearalgebra/GF2nPolynomial.java @@ -0,0 +1,587 @@ +package org.bouncycastle.pqc.math.linearalgebra; + + +/** + * This class implements polynomials over GF2nElements. + * + * @see GF2nElement + */ + +public class GF2nPolynomial +{ + + private GF2nElement[] coeff; // keeps the coefficients of this polynomial + + private int size; // the size of this polynomial + + /** + * Creates a new PolynomialGF2n of size <i>deg</i> and elem as + * coefficients. + * + * @param deg - + * the maximum degree + 1 + * @param elem - + * a GF2nElement + */ + public GF2nPolynomial(int deg, GF2nElement elem) + { + size = deg; + coeff = new GF2nElement[size]; + for (int i = 0; i < size; i++) + { + coeff[i] = (GF2nElement)elem.clone(); + } + } + + /** + * Creates a new PolynomialGF2n of size <i>deg</i>. + * + * @param deg the maximum degree + 1 + */ + private GF2nPolynomial(int deg) + { + size = deg; + coeff = new GF2nElement[size]; + } + + /** + * Creates a new PolynomialGF2n by cloning the given PolynomialGF2n <i>a</i>. + * + * @param a the PolynomialGF2n to clone + */ + public GF2nPolynomial(GF2nPolynomial a) + { + int i; + coeff = new GF2nElement[a.size]; + size = a.size; + for (i = 0; i < size; i++) + { + coeff[i] = (GF2nElement)a.coeff[i].clone(); + } + } + + /** + * Creates a new PolynomialGF2n from the given Bitstring <i>polynomial</i> + * over the GF2nField <i>B1</i>. + * + * @param polynomial the Bitstring to use + * @param B1 the field + */ + public GF2nPolynomial(GF2Polynomial polynomial, GF2nField B1) + { + size = B1.getDegree() + 1; + coeff = new GF2nElement[size]; + int i; + if (B1 instanceof GF2nONBField) + { + for (i = 0; i < size; i++) + { + if (polynomial.testBit(i)) + { + coeff[i] = GF2nONBElement.ONE((GF2nONBField)B1); + } + else + { + coeff[i] = GF2nONBElement.ZERO((GF2nONBField)B1); + } + } + } + else if (B1 instanceof GF2nPolynomialField) + { + for (i = 0; i < size; i++) + { + if (polynomial.testBit(i)) + { + coeff[i] = GF2nPolynomialElement + .ONE((GF2nPolynomialField)B1); + } + else + { + coeff[i] = GF2nPolynomialElement + .ZERO((GF2nPolynomialField)B1); + } + } + } + else + { + throw new IllegalArgumentException( + "PolynomialGF2n(Bitstring, GF2nField): B1 must be " + + "an instance of GF2nONBField or GF2nPolynomialField!"); + } + } + + public final void assignZeroToElements() + { + int i; + for (i = 0; i < size; i++) + { + coeff[i].assignZero(); + } + } + + /** + * Returns the size (=maximum degree + 1) of this PolynomialGF2n. This is + * not the degree, use getDegree instead. + * + * @return the size (=maximum degree + 1) of this PolynomialGF2n. + */ + public final int size() + { + return size; + } + + /** + * Returns the degree of this PolynomialGF2n. + * + * @return the degree of this PolynomialGF2n. + */ + public final int getDegree() + { + int i; + for (i = size - 1; i >= 0; i--) + { + if (!coeff[i].isZero()) + { + return i; + } + } + return -1; + } + + /** + * Enlarges the size of this PolynomialGF2n to <i>k</i> + 1. + * + * @param k the new maximum degree + */ + public final void enlarge(int k) + { + if (k <= size) + { + return; + } + int i; + GF2nElement[] res = new GF2nElement[k]; + System.arraycopy(coeff, 0, res, 0, size); + GF2nField f = coeff[0].getField(); + if (coeff[0] instanceof GF2nPolynomialElement) + { + for (i = size; i < k; i++) + { + res[i] = GF2nPolynomialElement.ZERO((GF2nPolynomialField)f); + } + } + else if (coeff[0] instanceof GF2nONBElement) + { + for (i = size; i < k; i++) + { + res[i] = GF2nONBElement.ZERO((GF2nONBField)f); + } + } + size = k; + coeff = res; + } + + public final void shrink() + { + int i = size - 1; + while (coeff[i].isZero() && (i > 0)) + { + i--; + } + i++; + if (i < size) + { + GF2nElement[] res = new GF2nElement[i]; + System.arraycopy(coeff, 0, res, 0, i); + coeff = res; + size = i; + } + } + + /** + * Sets the coefficient at <i>index</i> to <i>elem</i>. + * + * @param index the index + * @param elem the GF2nElement to store as coefficient <i>index</i> + */ + public final void set(int index, GF2nElement elem) + { + if (!(elem instanceof GF2nPolynomialElement) + && !(elem instanceof GF2nONBElement)) + { + throw new IllegalArgumentException( + "PolynomialGF2n.set f must be an " + + "instance of either GF2nPolynomialElement or GF2nONBElement!"); + } + coeff[index] = (GF2nElement)elem.clone(); + } + + /** + * Returns the coefficient at <i>index</i>. + * + * @param index the index + * @return the GF2nElement stored as coefficient <i>index</i> + */ + public final GF2nElement at(int index) + { + return coeff[index]; + } + + /** + * Returns true if all coefficients equal zero. + * + * @return true if all coefficients equal zero. + */ + public final boolean isZero() + { + int i; + for (i = 0; i < size; i++) + { + if (coeff[i] != null) + { + if (!coeff[i].isZero()) + { + return false; + } + } + } + return true; + } + + public final boolean equals(Object other) + { + if (other == null || !(other instanceof GF2nPolynomial)) + { + return false; + } + + GF2nPolynomial otherPol = (GF2nPolynomial)other; + + if (getDegree() != otherPol.getDegree()) + { + return false; + } + int i; + for (i = 0; i < size; i++) + { + if (!coeff[i].equals(otherPol.coeff[i])) + { + return false; + } + } + return true; + } + + /** + * @return the hash code of this polynomial + */ + public int hashCode() + { + return getDegree() + coeff.hashCode(); + } + + /** + * Adds the PolynomialGF2n <tt>b</tt> to <tt>this</tt> and returns the + * result in a new <tt>PolynomialGF2n</tt>. + * + * @param b - + * the <tt>PolynomialGF2n</tt> to add + * @return <tt>this + b</tt> + * @throws DifferentFieldsException if <tt>this</tt> and <tt>b</tt> are not defined over + * the same field. + */ + public final GF2nPolynomial add(GF2nPolynomial b) + throws RuntimeException + { + GF2nPolynomial result; + if (size() >= b.size()) + { + result = new GF2nPolynomial(size()); + int i; + for (i = 0; i < b.size(); i++) + { + result.coeff[i] = (GF2nElement)coeff[i].add(b.coeff[i]); + } + for (; i < size(); i++) + { + result.coeff[i] = coeff[i]; + } + } + else + { + result = new GF2nPolynomial(b.size()); + int i; + for (i = 0; i < size(); i++) + { + result.coeff[i] = (GF2nElement)coeff[i].add(b.coeff[i]); + } + for (; i < b.size(); i++) + { + result.coeff[i] = b.coeff[i]; + } + } + return result; + } + + /** + * Multiplies the scalar <i>s</i> to each coefficient of this + * PolynomialGF2n and returns the result in a new PolynomialGF2n. + * + * @param s the scalar to multiply + * @return <i>this</i> x <i>s</i> + * @throws DifferentFieldsException if <tt>this</tt> and <tt>s</tt> are not defined over + * the same field. + */ + public final GF2nPolynomial scalarMultiply(GF2nElement s) + throws RuntimeException + { + GF2nPolynomial result = new GF2nPolynomial(size()); + int i; + for (i = 0; i < size(); i++) + { + result.coeff[i] = (GF2nElement)coeff[i].multiply(s); // result[i] + // = + // a[i]*s + } + return result; + } + + /** + * Multiplies <i>this</i> by <i>b</i> and returns the result in a new + * PolynomialGF2n. + * + * @param b the PolynomialGF2n to multiply + * @return <i>this</i> * <i>b</i> + * @throws DifferentFieldsException if <tt>this</tt> and <tt>b</tt> are not defined over + * the same field. + */ + public final GF2nPolynomial multiply(GF2nPolynomial b) + throws RuntimeException + { + int i, j; + int aDegree = size(); + int bDegree = b.size(); + if (aDegree != bDegree) + { + throw new IllegalArgumentException( + "PolynomialGF2n.multiply: this and b must " + + "have the same size!"); + } + GF2nPolynomial result = new GF2nPolynomial((aDegree << 1) - 1); + for (i = 0; i < size(); i++) + { + for (j = 0; j < b.size(); j++) + { + if (result.coeff[i + j] == null) + { + result.coeff[i + j] = (GF2nElement)coeff[i] + .multiply(b.coeff[j]); + } + else + { + result.coeff[i + j] = (GF2nElement)result.coeff[i + j] + .add(coeff[i].multiply(b.coeff[j])); + } + } + } + return result; + } + + /** + * Multiplies <i>this</i> by <i>b</i>, reduces the result by <i>g</i> and + * returns it in a new PolynomialGF2n. + * + * @param b the PolynomialGF2n to multiply + * @param g the modul + * @return <i>this</i> * <i>b</i> mod <i>g</i> + * @throws DifferentFieldsException if <tt>this</tt>, <tt>b</tt> and <tt>g</tt> are + * not all defined over the same field. + */ + public final GF2nPolynomial multiplyAndReduce(GF2nPolynomial b, + GF2nPolynomial g) + throws RuntimeException, + ArithmeticException + { + return multiply(b).reduce(g); + } + + /** + * Reduces <i>this</i> by <i>g</i> and returns the result in a new + * PolynomialGF2n. + * + * @param g - + * the modulus + * @return <i>this</i> % <i>g</i> + * @throws DifferentFieldsException if <tt>this</tt> and <tt>g</tt> are not defined over + * the same field. + */ + public final GF2nPolynomial reduce(GF2nPolynomial g) + throws RuntimeException, ArithmeticException + { + return remainder(g); // return this % g + } + + /** + * Shifts left <i>this</i> by <i>amount</i> and stores the result in + * <i>this</i> PolynomialGF2n. + * + * @param amount the amount to shift the coefficients + */ + public final void shiftThisLeft(int amount) + { + if (amount > 0) + { + int i; + int oldSize = size; + GF2nField f = coeff[0].getField(); + enlarge(size + amount); + for (i = oldSize - 1; i >= 0; i--) + { + coeff[i + amount] = coeff[i]; + } + if (coeff[0] instanceof GF2nPolynomialElement) + { + for (i = amount - 1; i >= 0; i--) + { + coeff[i] = GF2nPolynomialElement + .ZERO((GF2nPolynomialField)f); + } + } + else if (coeff[0] instanceof GF2nONBElement) + { + for (i = amount - 1; i >= 0; i--) + { + coeff[i] = GF2nONBElement.ZERO((GF2nONBField)f); + } + } + } + } + + public final GF2nPolynomial shiftLeft(int amount) + { + if (amount <= 0) + { + return new GF2nPolynomial(this); + } + GF2nPolynomial result = new GF2nPolynomial(size + amount, coeff[0]); + result.assignZeroToElements(); + for (int i = 0; i < size; i++) + { + result.coeff[i + amount] = coeff[i]; + } + return result; + } + + /** + * Divides <i>this</i> by <i>b</i> and stores the result in a new + * PolynomialGF2n[2], quotient in result[0] and remainder in result[1]. + * + * @param b the divisor + * @return the quotient and remainder of <i>this</i> / <i>b</i> + * @throws DifferentFieldsException if <tt>this</tt> and <tt>b</tt> are not defined over + * the same field. + */ + public final GF2nPolynomial[] divide(GF2nPolynomial b) + throws RuntimeException, ArithmeticException + { + GF2nPolynomial[] result = new GF2nPolynomial[2]; + GF2nPolynomial a = new GF2nPolynomial(this); + a.shrink(); + GF2nPolynomial shift; + GF2nElement factor; + int bDegree = b.getDegree(); + GF2nElement inv = (GF2nElement)b.coeff[bDegree].invert(); + if (a.getDegree() < bDegree) + { + result[0] = new GF2nPolynomial(this); + result[0].assignZeroToElements(); + result[0].shrink(); + result[1] = new GF2nPolynomial(this); + result[1].shrink(); + return result; + } + result[0] = new GF2nPolynomial(this); + result[0].assignZeroToElements(); + int i = a.getDegree() - bDegree; + while (i >= 0) + { + factor = (GF2nElement)a.coeff[a.getDegree()].multiply(inv); + shift = b.scalarMultiply(factor); + shift.shiftThisLeft(i); + a = a.add(shift); + a.shrink(); + result[0].coeff[i] = (GF2nElement)factor.clone(); + i = a.getDegree() - bDegree; + } + result[1] = a; + result[0].shrink(); + return result; + } + + /** + * Divides <i>this</i> by <i>b</i> and stores the remainder in a new + * PolynomialGF2n. + * + * @param b the divisor + * @return the remainder <i>this</i> % <i>b</i> + * @throws DifferentFieldsException if <tt>this</tt> and <tt>b</tt> are not defined over + * the same field. + */ + public final GF2nPolynomial remainder(GF2nPolynomial b) + throws RuntimeException, ArithmeticException + { + GF2nPolynomial[] result = new GF2nPolynomial[2]; + result = divide(b); + return result[1]; + } + + /** + * Divides <i>this</i> by <i>b</i> and stores the quotient in a new + * PolynomialGF2n. + * + * @param b the divisor + * @return the quotient <i>this</i> / <i>b</i> + * @throws DifferentFieldsException if <tt>this</tt> and <tt>b</tt> are not defined over + * the same field. + */ + public final GF2nPolynomial quotient(GF2nPolynomial b) + throws RuntimeException, ArithmeticException + { + GF2nPolynomial[] result = new GF2nPolynomial[2]; + result = divide(b); + return result[0]; + } + + /** + * Computes the greatest common divisor of <i>this</i> and <i>g</i> and + * returns the result in a new PolynomialGF2n. + * + * @param g - + * a GF2nPolynomial + * @return gcd(<i>this</i>, <i>g</i>) + * @throws DifferentFieldsException if the coefficients of <i>this</i> and <i>g</i> use + * different fields + * @throws ArithmeticException if coefficients are zero. + */ + public final GF2nPolynomial gcd(GF2nPolynomial g) + throws RuntimeException, ArithmeticException + { + GF2nPolynomial a = new GF2nPolynomial(this); + GF2nPolynomial b = new GF2nPolynomial(g); + a.shrink(); + b.shrink(); + GF2nPolynomial c; + GF2nPolynomial result; + GF2nElement alpha; + while (!b.isZero()) + { + c = a.remainder(b); + a = b; + b = c; + } + alpha = a.coeff[a.getDegree()]; + result = a.scalarMultiply((GF2nElement)alpha.invert()); + return result; + } + +} |