diff options
author | David Hook <dgh@cryptoworkshop.com> | 2013-05-31 11:07:45 +0400 |
---|---|---|
committer | David Hook <dgh@cryptoworkshop.com> | 2013-05-31 11:07:45 +0400 |
commit | 2b976f5364cfdbc37d3086019d93483c983eb80b (patch) | |
tree | cb846af3fd1d43f9c2562a1fb2d06b997ad8f229 /core/src/main/java/org/bouncycastle/pqc/math/linearalgebra/PolynomialRingGF2m.java | |
parent | 5f714bd92fbd780d22406f4bc3681be005f6f04a (diff) |
initial reshuffle
Diffstat (limited to 'core/src/main/java/org/bouncycastle/pqc/math/linearalgebra/PolynomialRingGF2m.java')
-rw-r--r-- | core/src/main/java/org/bouncycastle/pqc/math/linearalgebra/PolynomialRingGF2m.java | 175 |
1 files changed, 175 insertions, 0 deletions
diff --git a/core/src/main/java/org/bouncycastle/pqc/math/linearalgebra/PolynomialRingGF2m.java b/core/src/main/java/org/bouncycastle/pqc/math/linearalgebra/PolynomialRingGF2m.java new file mode 100644 index 00000000..0711583b --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/math/linearalgebra/PolynomialRingGF2m.java @@ -0,0 +1,175 @@ +package org.bouncycastle.pqc.math.linearalgebra; + +/** + * This class represents polynomial rings <tt>GF(2^m)[X]/p(X)</tt> for + * <tt>m<<;32</tt>. If <tt>p(X)</tt> is irreducible, the polynomial ring + * is in fact an extension field of <tt>GF(2^m)</tt>. + */ +public class PolynomialRingGF2m +{ + + /** + * the finite field this polynomial ring is defined over + */ + private GF2mField field; + + /** + * the reduction polynomial + */ + private PolynomialGF2mSmallM p; + + /** + * the squaring matrix for this polynomial ring (given as the array of its + * row vectors) + */ + protected PolynomialGF2mSmallM[] sqMatrix; + + /** + * the matrix for computing square roots in this polynomial ring (given as + * the array of its row vectors). This matrix is computed as the inverse of + * the squaring matrix. + */ + protected PolynomialGF2mSmallM[] sqRootMatrix; + + /** + * Constructor. + * + * @param field the finite field + * @param p the reduction polynomial + */ + public PolynomialRingGF2m(GF2mField field, PolynomialGF2mSmallM p) + { + this.field = field; + this.p = p; + computeSquaringMatrix(); + computeSquareRootMatrix(); + } + + /** + * @return the squaring matrix for this polynomial ring + */ + public PolynomialGF2mSmallM[] getSquaringMatrix() + { + return sqMatrix; + } + + /** + * @return the matrix for computing square roots for this polynomial ring + */ + public PolynomialGF2mSmallM[] getSquareRootMatrix() + { + return sqRootMatrix; + } + + /** + * Compute the squaring matrix for this polynomial ring, using the base + * field and the reduction polynomial. + */ + private void computeSquaringMatrix() + { + int numColumns = p.getDegree(); + sqMatrix = new PolynomialGF2mSmallM[numColumns]; + for (int i = 0; i < numColumns >> 1; i++) + { + int[] monomCoeffs = new int[(i << 1) + 1]; + monomCoeffs[i << 1] = 1; + sqMatrix[i] = new PolynomialGF2mSmallM(field, monomCoeffs); + } + for (int i = numColumns >> 1; i < numColumns; i++) + { + int[] monomCoeffs = new int[(i << 1) + 1]; + monomCoeffs[i << 1] = 1; + PolynomialGF2mSmallM monomial = new PolynomialGF2mSmallM(field, + monomCoeffs); + sqMatrix[i] = monomial.mod(p); + } + } + + /** + * Compute the matrix for computing square roots in this polynomial ring by + * inverting the squaring matrix. + */ + private void computeSquareRootMatrix() + { + int numColumns = p.getDegree(); + + // clone squaring matrix + PolynomialGF2mSmallM[] tmpMatrix = new PolynomialGF2mSmallM[numColumns]; + for (int i = numColumns - 1; i >= 0; i--) + { + tmpMatrix[i] = new PolynomialGF2mSmallM(sqMatrix[i]); + } + + // initialize square root matrix as unit matrix + sqRootMatrix = new PolynomialGF2mSmallM[numColumns]; + for (int i = numColumns - 1; i >= 0; i--) + { + sqRootMatrix[i] = new PolynomialGF2mSmallM(field, i); + } + + // simultaneously compute Gaussian reduction of squaring matrix and unit + // matrix + for (int i = 0; i < numColumns; i++) + { + // if diagonal element is zero + if (tmpMatrix[i].getCoefficient(i) == 0) + { + boolean foundNonZero = false; + // find a non-zero element in the same row + for (int j = i + 1; j < numColumns; j++) + { + if (tmpMatrix[j].getCoefficient(i) != 0) + { + // found it, swap columns ... + foundNonZero = true; + swapColumns(tmpMatrix, i, j); + swapColumns(sqRootMatrix, i, j); + // ... and quit searching + j = numColumns; + continue; + } + } + // if no non-zero element was found + if (!foundNonZero) + { + // the matrix is not invertible + throw new ArithmeticException( + "Squaring matrix is not invertible."); + } + } + + // normalize i-th column + int coef = tmpMatrix[i].getCoefficient(i); + int invCoef = field.inverse(coef); + tmpMatrix[i].multThisWithElement(invCoef); + sqRootMatrix[i].multThisWithElement(invCoef); + + // normalize all other columns + for (int j = 0; j < numColumns; j++) + { + if (j != i) + { + coef = tmpMatrix[j].getCoefficient(i); + if (coef != 0) + { + PolynomialGF2mSmallM tmpSqColumn = tmpMatrix[i] + .multWithElement(coef); + PolynomialGF2mSmallM tmpInvColumn = sqRootMatrix[i] + .multWithElement(coef); + tmpMatrix[j].addToThis(tmpSqColumn); + sqRootMatrix[j].addToThis(tmpInvColumn); + } + } + } + } + } + + private static void swapColumns(PolynomialGF2mSmallM[] matrix, int first, + int second) + { + PolynomialGF2mSmallM tmp = matrix[first]; + matrix[first] = matrix[second]; + matrix[second] = tmp; + } + +} |