diff options
Diffstat (limited to 'libraries/spongycastle/core/src/main/java/org/spongycastle/pqc/math/linearalgebra/GF2mMatrix.java')
-rw-r--r-- | libraries/spongycastle/core/src/main/java/org/spongycastle/pqc/math/linearalgebra/GF2mMatrix.java | 377 |
1 files changed, 0 insertions, 377 deletions
diff --git a/libraries/spongycastle/core/src/main/java/org/spongycastle/pqc/math/linearalgebra/GF2mMatrix.java b/libraries/spongycastle/core/src/main/java/org/spongycastle/pqc/math/linearalgebra/GF2mMatrix.java deleted file mode 100644 index fb2b1e4b8..000000000 --- a/libraries/spongycastle/core/src/main/java/org/spongycastle/pqc/math/linearalgebra/GF2mMatrix.java +++ /dev/null @@ -1,377 +0,0 @@ -package org.spongycastle.pqc.math.linearalgebra; - -/** - * This class describes some operations with matrices over finite field <i>GF(2<sup>m</sup>)</i> - * with small <i>m</i> (1< m <32). - * - * @see Matrix - */ -public class GF2mMatrix - extends Matrix -{ - - /** - * finite field GF(2^m) - */ - protected GF2mField field; - - /** - * For the matrix representation the array of type int[][] is used, thus - * every element of the array keeps one element of the matrix (element from - * finite field GF(2^m)) - */ - protected int[][] matrix; - - /** - * Constructor. - * - * @param field a finite field GF(2^m) - * @param enc byte[] matrix in byte array form - */ - public GF2mMatrix(GF2mField field, byte[] enc) - { - - this.field = field; - - // decode matrix - int d = 8; - int count = 1; - while (field.getDegree() > d) - { - count++; - d += 8; - } - - if (enc.length < 5) - { - throw new IllegalArgumentException( - " Error: given array is not encoded matrix over GF(2^m)"); - } - - this.numRows = ((enc[3] & 0xff) << 24) ^ ((enc[2] & 0xff) << 16) - ^ ((enc[1] & 0xff) << 8) ^ (enc[0] & 0xff); - - int n = count * this.numRows; - - if ((this.numRows <= 0) || (((enc.length - 4) % n) != 0)) - { - throw new IllegalArgumentException( - " Error: given array is not encoded matrix over GF(2^m)"); - } - - this.numColumns = (enc.length - 4) / n; - - matrix = new int[this.numRows][this.numColumns]; - count = 4; - for (int i = 0; i < this.numRows; i++) - { - for (int j = 0; j < this.numColumns; j++) - { - for (int jj = 0; jj < d; jj += 8) - { - matrix[i][j] ^= (enc[count++] & 0x000000ff) << jj; - } - if (!this.field.isElementOfThisField(matrix[i][j])) - { - throw new IllegalArgumentException( - " Error: given array is not encoded matrix over GF(2^m)"); - } - } - } - } - - /** - * Copy constructor. - * - * @param other another {@link GF2mMatrix} - */ - public GF2mMatrix(GF2mMatrix other) - { - numRows = other.numRows; - numColumns = other.numColumns; - field = other.field; - matrix = new int[numRows][]; - for (int i = 0; i < numRows; i++) - { - matrix[i] = IntUtils.clone(other.matrix[i]); - } - } - - /** - * Constructor. - * - * @param field a finite field GF(2^m) - * @param matrix the matrix as int array. Only the reference is copied. - */ - protected GF2mMatrix(GF2mField field, int[][] matrix) - { - this.field = field; - this.matrix = matrix; - numRows = matrix.length; - numColumns = matrix[0].length; - } - - /** - * @return a byte array encoding of this matrix - */ - public byte[] getEncoded() - { - int d = 8; - int count = 1; - while (field.getDegree() > d) - { - count++; - d += 8; - } - - byte[] bf = new byte[this.numRows * this.numColumns * count + 4]; - bf[0] = (byte)(this.numRows & 0xff); - bf[1] = (byte)((this.numRows >>> 8) & 0xff); - bf[2] = (byte)((this.numRows >>> 16) & 0xff); - bf[3] = (byte)((this.numRows >>> 24) & 0xff); - - count = 4; - for (int i = 0; i < this.numRows; i++) - { - for (int j = 0; j < this.numColumns; j++) - { - for (int jj = 0; jj < d; jj += 8) - { - bf[count++] = (byte)(matrix[i][j] >>> jj); - } - } - } - - return bf; - } - - /** - * Check if this is the zero matrix (i.e., all entries are zero). - * - * @return <tt>true</tt> if this is the zero matrix - */ - public boolean isZero() - { - for (int i = 0; i < numRows; i++) - { - for (int j = 0; j < numColumns; j++) - { - if (matrix[i][j] != 0) - { - return false; - } - } - } - return true; - } - - /** - * Compute the inverse of this matrix. - * - * @return the inverse of this matrix (newly created). - */ - public Matrix computeInverse() - { - if (numRows != numColumns) - { - throw new ArithmeticException("Matrix is not invertible."); - } - - // clone this matrix - int[][] tmpMatrix = new int[numRows][numRows]; - for (int i = numRows - 1; i >= 0; i--) - { - tmpMatrix[i] = IntUtils.clone(matrix[i]); - } - - // initialize inverse matrix as unit matrix - int[][] invMatrix = new int[numRows][numRows]; - for (int i = numRows - 1; i >= 0; i--) - { - invMatrix[i][i] = 1; - } - - // simultaneously compute Gaussian reduction of tmpMatrix and unit - // matrix - for (int i = 0; i < numRows; i++) - { - // if diagonal element is zero - if (tmpMatrix[i][i] == 0) - { - boolean foundNonZero = false; - // find a non-zero element in the same column - for (int j = i + 1; j < numRows; j++) - { - if (tmpMatrix[j][i] != 0) - { - // found it, swap rows ... - foundNonZero = true; - swapColumns(tmpMatrix, i, j); - swapColumns(invMatrix, i, j); - // ... and quit searching - j = numRows; - continue; - } - } - // if no non-zero element was found - if (!foundNonZero) - { - // the matrix is not invertible - throw new ArithmeticException("Matrix is not invertible."); - } - } - - // normalize i-th row - int coef = tmpMatrix[i][i]; - int invCoef = field.inverse(coef); - multRowWithElementThis(tmpMatrix[i], invCoef); - multRowWithElementThis(invMatrix[i], invCoef); - - // normalize all other rows - for (int j = 0; j < numRows; j++) - { - if (j != i) - { - coef = tmpMatrix[j][i]; - if (coef != 0) - { - int[] tmpRow = multRowWithElement(tmpMatrix[i], coef); - int[] tmpInvRow = multRowWithElement(invMatrix[i], coef); - addToRow(tmpRow, tmpMatrix[j]); - addToRow(tmpInvRow, invMatrix[j]); - } - } - } - } - - return new GF2mMatrix(field, invMatrix); - } - - private static void swapColumns(int[][] matrix, int first, int second) - { - int[] tmp = matrix[first]; - matrix[first] = matrix[second]; - matrix[second] = tmp; - } - - private void multRowWithElementThis(int[] row, int element) - { - for (int i = row.length - 1; i >= 0; i--) - { - row[i] = field.mult(row[i], element); - } - } - - private int[] multRowWithElement(int[] row, int element) - { - int[] result = new int[row.length]; - for (int i = row.length - 1; i >= 0; i--) - { - result[i] = field.mult(row[i], element); - } - return result; - } - - /** - * Add one row to another. - * - * @param fromRow the addend - * @param toRow the row to add to - */ - private void addToRow(int[] fromRow, int[] toRow) - { - for (int i = toRow.length - 1; i >= 0; i--) - { - toRow[i] = field.add(fromRow[i], toRow[i]); - } - } - - public Matrix rightMultiply(Matrix a) - { - throw new RuntimeException("Not implemented."); - } - - public Matrix rightMultiply(Permutation perm) - { - throw new RuntimeException("Not implemented."); - } - - public Vector leftMultiply(Vector vector) - { - throw new RuntimeException("Not implemented."); - } - - public Vector rightMultiply(Vector vector) - { - throw new RuntimeException("Not implemented."); - } - - /** - * Checks if given object is equal to this matrix. The method returns false - * whenever the given object is not a matrix over GF(2^m). - * - * @param other object - * @return true or false - */ - public boolean equals(Object other) - { - - if (other == null || !(other instanceof GF2mMatrix)) - { - return false; - } - - GF2mMatrix otherMatrix = (GF2mMatrix)other; - - if ((!this.field.equals(otherMatrix.field)) - || (otherMatrix.numRows != this.numColumns) - || (otherMatrix.numColumns != this.numColumns)) - { - return false; - } - - for (int i = 0; i < this.numRows; i++) - { - for (int j = 0; j < this.numColumns; j++) - { - if (this.matrix[i][j] != otherMatrix.matrix[i][j]) - { - return false; - } - } - } - - return true; - } - - public int hashCode() - { - int hash = (this.field.hashCode() * 31 + numRows) * 31 + numColumns; - for (int i = 0; i < this.numRows; i++) - { - for (int j = 0; j < this.numColumns; j++) - { - hash = hash * 31 + matrix[i][j]; - } - } - return hash; - } - - public String toString() - { - String str = this.numRows + " x " + this.numColumns + " Matrix over " - + this.field.toString() + ": \n"; - - for (int i = 0; i < this.numRows; i++) - { - for (int j = 0; j < this.numColumns; j++) - { - str = str + this.field.elementToStr(matrix[i][j]) + " : "; - } - str = str + "\n"; - } - - return str; - } - -} |