diff options
Diffstat (limited to 'core/src/main/java/org/spongycastle/pqc/math/linearalgebra/GF2nPolynomialField.java')
| -rw-r--r-- | core/src/main/java/org/spongycastle/pqc/math/linearalgebra/GF2nPolynomialField.java | 553 |
1 files changed, 553 insertions, 0 deletions
diff --git a/core/src/main/java/org/spongycastle/pqc/math/linearalgebra/GF2nPolynomialField.java b/core/src/main/java/org/spongycastle/pqc/math/linearalgebra/GF2nPolynomialField.java new file mode 100644 index 00000000..f9ec0bca --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/math/linearalgebra/GF2nPolynomialField.java @@ -0,0 +1,553 @@ +package org.spongycastle.pqc.math.linearalgebra; + + +import java.util.Random; +import java.util.Vector; + + +/** + * This class implements the abstract class <tt>GF2nField</tt> for polynomial + * representation. It computes the field polynomial and the squaring matrix. + * GF2nField is used by GF2nPolynomialElement which implements the elements of + * this field. + * + * @see GF2nField + * @see GF2nPolynomialElement + */ +public class GF2nPolynomialField + extends GF2nField +{ + + /** + * Matrix used for fast squaring + */ + GF2Polynomial[] squaringMatrix; + + // field polynomial is a trinomial + private boolean isTrinomial = false; + + // field polynomial is a pentanomial + private boolean isPentanomial = false; + + // middle coefficient of the field polynomial in case it is a trinomial + private int tc; + + // middle 3 coefficients of the field polynomial in case it is a pentanomial + private int[] pc = new int[3]; + + /** + * constructs an instance of the finite field with 2<sup>deg</sup> + * elements and characteristic 2. + * + * @param deg the extention degree of this field + */ + public GF2nPolynomialField(int deg) + { + if (deg < 3) + { + throw new IllegalArgumentException("k must be at least 3"); + } + mDegree = deg; + computeFieldPolynomial(); + computeSquaringMatrix(); + fields = new Vector(); + matrices = new Vector(); + } + + /** + * constructs an instance of the finite field with 2<sup>deg</sup> + * elements and characteristic 2. + * + * @param deg the degree of this field + * @param file true if you want to read the field polynomial from the + * file false if you want to use a random fielpolynomial + * (this can take very long for huge degrees) + */ + public GF2nPolynomialField(int deg, boolean file) + { + if (deg < 3) + { + throw new IllegalArgumentException("k must be at least 3"); + } + mDegree = deg; + if (file) + { + computeFieldPolynomial(); + } + else + { + computeFieldPolynomial2(); + } + computeSquaringMatrix(); + fields = new Vector(); + matrices = new Vector(); + } + + /** + * Creates a new GF2nField of degree <i>i</i> and uses the given + * <i>polynomial</i> as field polynomial. The <i>polynomial</i> is checked + * whether it is irreducible. This can take some time if <i>i</i> is huge! + * + * @param deg degree of the GF2nField + * @param polynomial the field polynomial to use + * @throws PolynomialIsNotIrreducibleException if the given polynomial is not irreducible in GF(2^<i>i</i>) + */ + public GF2nPolynomialField(int deg, GF2Polynomial polynomial) + throws RuntimeException + { + if (deg < 3) + { + throw new IllegalArgumentException("degree must be at least 3"); + } + if (polynomial.getLength() != deg + 1) + { + throw new RuntimeException(); + } + if (!polynomial.isIrreducible()) + { + throw new RuntimeException(); + } + mDegree = deg; + // fieldPolynomial = new Bitstring(polynomial); + fieldPolynomial = polynomial; + computeSquaringMatrix(); + int k = 2; // check if the polynomial is a trinomial or pentanomial + for (int j = 1; j < fieldPolynomial.getLength() - 1; j++) + { + if (fieldPolynomial.testBit(j)) + { + k++; + if (k == 3) + { + tc = j; + } + if (k <= 5) + { + pc[k - 3] = j; + } + } + } + if (k == 3) + { + isTrinomial = true; + } + if (k == 5) + { + isPentanomial = true; + } + fields = new Vector(); + matrices = new Vector(); + } + + /** + * Returns true if the field polynomial is a trinomial. The coefficient can + * be retrieved using getTc(). + * + * @return true if the field polynomial is a trinomial + */ + public boolean isTrinomial() + { + return isTrinomial; + } + + /** + * Returns true if the field polynomial is a pentanomial. The coefficients + * can be retrieved using getPc(). + * + * @return true if the field polynomial is a pentanomial + */ + public boolean isPentanomial() + { + return isPentanomial; + } + + /** + * Returns the degree of the middle coefficient of the used field trinomial + * (x^n + x^(getTc()) + 1). + * + * @return the middle coefficient of the used field trinomial + * @throws GFException if the field polynomial is not a trinomial + */ + public int getTc() + throws RuntimeException + { + if (!isTrinomial) + { + throw new RuntimeException(); + } + return tc; + } + + /** + * Returns the degree of the middle coefficients of the used field + * pentanomial (x^n + x^(getPc()[2]) + x^(getPc()[1]) + x^(getPc()[0]) + 1). + * + * @return the middle coefficients of the used field pentanomial + * @throws GFException if the field polynomial is not a pentanomial + */ + public int[] getPc() + throws RuntimeException + { + if (!isPentanomial) + { + throw new RuntimeException(); + } + int[] result = new int[3]; + System.arraycopy(pc, 0, result, 0, 3); + return result; + } + + /** + * Return row vector i of the squaring matrix. + * + * @param i the index of the row vector to return + * @return a copy of squaringMatrix[i] + * @see GF2nPolynomialElement#squareMatrix + */ + public GF2Polynomial getSquaringVector(int i) + { + return new GF2Polynomial(squaringMatrix[i]); + } + + /** + * Compute a random root of the given GF2Polynomial. + * + * @param polynomial the polynomial + * @return a random root of <tt>polynomial</tt> + */ + protected GF2nElement getRandomRoot(GF2Polynomial polynomial) + { + // We are in B1!!! + GF2nPolynomial c; + GF2nPolynomial ut; + GF2nElement u; + GF2nPolynomial h; + int hDegree; + // 1. Set g(t) <- f(t) + GF2nPolynomial g = new GF2nPolynomial(polynomial, this); + int gDegree = g.getDegree(); + int i; + + // 2. while deg(g) > 1 + while (gDegree > 1) + { + do + { + // 2.1 choose random u (element of) GF(2^m) + u = new GF2nPolynomialElement(this, new Random()); + ut = new GF2nPolynomial(2, GF2nPolynomialElement.ZERO(this)); + // 2.2 Set c(t) <- ut + ut.set(1, u); + c = new GF2nPolynomial(ut); + // 2.3 For i from 1 to m-1 do + for (i = 1; i <= mDegree - 1; i++) + { + // 2.3.1 c(t) <- (c(t)^2 + ut) mod g(t) + c = c.multiplyAndReduce(c, g); + c = c.add(ut); + } + // 2.4 set h(t) <- GCD(c(t), g(t)) + h = c.gcd(g); + // 2.5 if h(t) is constant or deg(g) = deg(h) then go to + // step 2.1 + hDegree = h.getDegree(); + gDegree = g.getDegree(); + } + while ((hDegree == 0) || (hDegree == gDegree)); + // 2.6 If 2deg(h) > deg(g) then set g(t) <- g(t)/h(t) ... + if ((hDegree << 1) > gDegree) + { + g = g.quotient(h); + } + else + { + // ... else g(t) <- h(t) + g = new GF2nPolynomial(h); + } + gDegree = g.getDegree(); + } + // 3. Output g(0) + return g.at(0); + + } + + /** + * Computes the change-of-basis matrix for basis conversion according to + * 1363. The result is stored in the lists fields and matrices. + * + * @param B1 the GF2nField to convert to + * @see "P1363 A.7.3, p111ff" + */ + protected void computeCOBMatrix(GF2nField B1) + { + // we are in B0 here! + if (mDegree != B1.mDegree) + { + throw new IllegalArgumentException( + "GF2nPolynomialField.computeCOBMatrix: B1 has a different " + + "degree and thus cannot be coverted to!"); + } + if (B1 instanceof GF2nONBField) + { + // speedup (calculation is done in PolynomialElements instead of + // ONB) + B1.computeCOBMatrix(this); + return; + } + int i, j; + GF2nElement[] gamma; + GF2nElement u; + GF2Polynomial[] COBMatrix = new GF2Polynomial[mDegree]; + for (i = 0; i < mDegree; i++) + { + COBMatrix[i] = new GF2Polynomial(mDegree); + } + + // find Random Root + do + { + // u is in representation according to B1 + u = B1.getRandomRoot(fieldPolynomial); + } + while (u.isZero()); + + // build gamma matrix by multiplying by u + if (u instanceof GF2nONBElement) + { + gamma = new GF2nONBElement[mDegree]; + gamma[mDegree - 1] = GF2nONBElement.ONE((GF2nONBField)B1); + } + else + { + gamma = new GF2nPolynomialElement[mDegree]; + gamma[mDegree - 1] = GF2nPolynomialElement + .ONE((GF2nPolynomialField)B1); + } + gamma[mDegree - 2] = u; + for (i = mDegree - 3; i >= 0; i--) + { + gamma[i] = (GF2nElement)gamma[i + 1].multiply(u); + } + if (B1 instanceof GF2nONBField) + { + // convert horizontal gamma matrix by vertical Bitstrings + for (i = 0; i < mDegree; i++) + { + for (j = 0; j < mDegree; j++) + { + // TODO remember: ONB treats its Bits in reverse order !!! + if (gamma[i].testBit(mDegree - j - 1)) + { + COBMatrix[mDegree - j - 1].setBit(mDegree - i - 1); + } + } + } + } + else + { + // convert horizontal gamma matrix by vertical Bitstrings + for (i = 0; i < mDegree; i++) + { + for (j = 0; j < mDegree; j++) + { + if (gamma[i].testBit(j)) + { + COBMatrix[mDegree - j - 1].setBit(mDegree - i - 1); + } + } + } + } + + // store field and matrix for further use + fields.addElement(B1); + matrices.addElement(COBMatrix); + // store field and inverse matrix for further use in B1 + B1.fields.addElement(this); + B1.matrices.addElement(invertMatrix(COBMatrix)); + } + + /** + * Computes a new squaring matrix used for fast squaring. + * + * @see GF2nPolynomialElement#square + */ + private void computeSquaringMatrix() + { + GF2Polynomial[] d = new GF2Polynomial[mDegree - 1]; + int i, j; + squaringMatrix = new GF2Polynomial[mDegree]; + for (i = 0; i < squaringMatrix.length; i++) + { + squaringMatrix[i] = new GF2Polynomial(mDegree, "ZERO"); + } + + for (i = 0; i < mDegree - 1; i++) + { + d[i] = new GF2Polynomial(1, "ONE").shiftLeft(mDegree + i) + .remainder(fieldPolynomial); + } + for (i = 1; i <= Math.abs(mDegree >> 1); i++) + { + for (j = 1; j <= mDegree; j++) + { + if (d[mDegree - (i << 1)].testBit(mDegree - j)) + { + squaringMatrix[j - 1].setBit(mDegree - i); + } + } + } + for (i = Math.abs(mDegree >> 1) + 1; i <= mDegree; i++) + { + squaringMatrix[(i << 1) - mDegree - 1].setBit(mDegree - i); + } + + } + + /** + * Computes the field polynomial. This can take a long time for big degrees. + */ + protected void computeFieldPolynomial() + { + if (testTrinomials()) + { + return; + } + if (testPentanomials()) + { + return; + } + testRandom(); + } + + /** + * Computes the field polynomial. This can take a long time for big degrees. + */ + protected void computeFieldPolynomial2() + { + if (testTrinomials()) + { + return; + } + if (testPentanomials()) + { + return; + } + testRandom(); + } + + /** + * Tests all trinomials of degree (n+1) until a irreducible is found and + * stores the result in <i>field polynomial</i>. Returns false if no + * irreducible trinomial exists in GF(2^n). This can take very long for huge + * degrees. + * + * @return true if an irreducible trinomial is found + */ + private boolean testTrinomials() + { + int i, l; + boolean done = false; + l = 0; + + fieldPolynomial = new GF2Polynomial(mDegree + 1); + fieldPolynomial.setBit(0); + fieldPolynomial.setBit(mDegree); + for (i = 1; (i < mDegree) && !done; i++) + { + fieldPolynomial.setBit(i); + done = fieldPolynomial.isIrreducible(); + l++; + if (done) + { + isTrinomial = true; + tc = i; + return done; + } + fieldPolynomial.resetBit(i); + done = fieldPolynomial.isIrreducible(); + } + + return done; + } + + /** + * Tests all pentanomials of degree (n+1) until a irreducible is found and + * stores the result in <i>field polynomial</i>. Returns false if no + * irreducible pentanomial exists in GF(2^n). This can take very long for + * huge degrees. + * + * @return true if an irreducible pentanomial is found + */ + private boolean testPentanomials() + { + int i, j, k, l; + boolean done = false; + l = 0; + + fieldPolynomial = new GF2Polynomial(mDegree + 1); + fieldPolynomial.setBit(0); + fieldPolynomial.setBit(mDegree); + for (i = 1; (i <= (mDegree - 3)) && !done; i++) + { + fieldPolynomial.setBit(i); + for (j = i + 1; (j <= (mDegree - 2)) && !done; j++) + { + fieldPolynomial.setBit(j); + for (k = j + 1; (k <= (mDegree - 1)) && !done; k++) + { + fieldPolynomial.setBit(k); + if (((mDegree & 1) != 0) | ((i & 1) != 0) | ((j & 1) != 0) + | ((k & 1) != 0)) + { + done = fieldPolynomial.isIrreducible(); + l++; + if (done) + { + isPentanomial = true; + pc[0] = i; + pc[1] = j; + pc[2] = k; + return done; + } + } + fieldPolynomial.resetBit(k); + } + fieldPolynomial.resetBit(j); + } + fieldPolynomial.resetBit(i); + } + + return done; + } + + /** + * Tests random polynomials of degree (n+1) until an irreducible is found + * and stores the result in <i>field polynomial</i>. This can take very + * long for huge degrees. + * + * @return true + */ + private boolean testRandom() + { + int l; + boolean done = false; + + fieldPolynomial = new GF2Polynomial(mDegree + 1); + l = 0; + while (!done) + { + l++; + fieldPolynomial.randomize(); + fieldPolynomial.setBit(mDegree); + fieldPolynomial.setBit(0); + if (fieldPolynomial.isIrreducible()) + { + done = true; + return done; + } + } + + return done; + } + +} |