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/GF2Matrix.java | |
parent | 5f714bd92fbd780d22406f4bc3681be005f6f04a (diff) |
initial reshuffle
Diffstat (limited to 'core/src/main/java/org/bouncycastle/pqc/math/linearalgebra/GF2Matrix.java')
-rw-r--r-- | core/src/main/java/org/bouncycastle/pqc/math/linearalgebra/GF2Matrix.java | 1323 |
1 files changed, 1323 insertions, 0 deletions
diff --git a/core/src/main/java/org/bouncycastle/pqc/math/linearalgebra/GF2Matrix.java b/core/src/main/java/org/bouncycastle/pqc/math/linearalgebra/GF2Matrix.java new file mode 100644 index 00000000..a61f9507 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/pqc/math/linearalgebra/GF2Matrix.java @@ -0,0 +1,1323 @@ +package org.bouncycastle.pqc.math.linearalgebra; + +import java.security.SecureRandom; + +/** + * This class describes some operations with matrices over finite field GF(2) + * and is used in ecc and MQ-PKC (also has some specific methods and + * implementation) + */ +public class GF2Matrix + extends Matrix +{ + + /** + * For the matrix representation the array of type int[][] is used, thus one + * element of the array keeps 32 elements of the matrix (from one row and 32 + * columns) + */ + private int[][] matrix; + + /** + * the length of each array representing a row of this matrix, computed as + * <tt>(numColumns + 31) / 32</tt> + */ + private int length; + + /** + * Create the matrix from encoded form. + * + * @param enc the encoded matrix + */ + public GF2Matrix(byte[] enc) + { + if (enc.length < 9) + { + throw new ArithmeticException( + "given array is not an encoded matrix over GF(2)"); + } + + numRows = LittleEndianConversions.OS2IP(enc, 0); + numColumns = LittleEndianConversions.OS2IP(enc, 4); + + int n = ((numColumns + 7) >>> 3) * numRows; + + if ((numRows <= 0) || (n != (enc.length - 8))) + { + throw new ArithmeticException( + "given array is not an encoded matrix over GF(2)"); + } + + length = (numColumns + 31) >>> 5; + matrix = new int[numRows][length]; + + // number of "full" integer + int q = numColumns >> 5; + // number of bits in non-full integer + int r = numColumns & 0x1f; + + int count = 8; + for (int i = 0; i < numRows; i++) + { + for (int j = 0; j < q; j++, count += 4) + { + matrix[i][j] = LittleEndianConversions.OS2IP(enc, count); + } + for (int j = 0; j < r; j += 8) + { + matrix[i][q] ^= (enc[count++] & 0xff) << j; + } + } + } + + /** + * Create the matrix with the contents of the given array. The matrix is not + * copied. Unused coefficients are masked out. + * + * @param numColumns the number of columns + * @param matrix the element array + */ + public GF2Matrix(int numColumns, int[][] matrix) + { + if (matrix[0].length != (numColumns + 31) >> 5) + { + throw new ArithmeticException( + "Int array does not match given number of columns."); + } + this.numColumns = numColumns; + numRows = matrix.length; + length = matrix[0].length; + int rest = numColumns & 0x1f; + int bitMask; + if (rest == 0) + { + bitMask = 0xffffffff; + } + else + { + bitMask = (1 << rest) - 1; + } + for (int i = 0; i < numRows; i++) + { + matrix[i][length - 1] &= bitMask; + } + this.matrix = matrix; + } + + /** + * Create an nxn matrix of the given type. + * + * @param n the number of rows (and columns) + * @param typeOfMatrix the martix type (see {@link Matrix} for predefined + * constants) + */ + public GF2Matrix(int n, char typeOfMatrix) + { + this(n, typeOfMatrix, new java.security.SecureRandom()); + } + + /** + * Create an nxn matrix of the given type. + * + * @param n the matrix size + * @param typeOfMatrix the matrix type + * @param sr the source of randomness + */ + public GF2Matrix(int n, char typeOfMatrix, SecureRandom sr) + { + if (n <= 0) + { + throw new ArithmeticException("Size of matrix is non-positive."); + } + + switch (typeOfMatrix) + { + + case Matrix.MATRIX_TYPE_ZERO: + assignZeroMatrix(n, n); + break; + + case Matrix.MATRIX_TYPE_UNIT: + assignUnitMatrix(n); + break; + + case Matrix.MATRIX_TYPE_RANDOM_LT: + assignRandomLowerTriangularMatrix(n, sr); + break; + + case Matrix.MATRIX_TYPE_RANDOM_UT: + assignRandomUpperTriangularMatrix(n, sr); + break; + + case Matrix.MATRIX_TYPE_RANDOM_REGULAR: + assignRandomRegularMatrix(n, sr); + break; + + default: + throw new ArithmeticException("Unknown matrix type."); + } + } + + /** + * Copy constructor. + * + * @param a another {@link GF2Matrix} + */ + public GF2Matrix(GF2Matrix a) + { + numColumns = a.getNumColumns(); + numRows = a.getNumRows(); + length = a.length; + matrix = new int[a.matrix.length][]; + for (int i = 0; i < matrix.length; i++) + { + matrix[i] = IntUtils.clone(a.matrix[i]); + } + + } + + /** + * create the mxn zero matrix + */ + private GF2Matrix(int m, int n) + { + if ((n <= 0) || (m <= 0)) + { + throw new ArithmeticException("size of matrix is non-positive"); + } + + assignZeroMatrix(m, n); + } + + /** + * Create the mxn zero matrix. + * + * @param m number of rows + * @param n number of columns + */ + private void assignZeroMatrix(int m, int n) + { + numRows = m; + numColumns = n; + length = (n + 31) >>> 5; + matrix = new int[numRows][length]; + for (int i = 0; i < numRows; i++) + { + for (int j = 0; j < length; j++) + { + matrix[i][j] = 0; + } + } + } + + /** + * Create the mxn unit matrix. + * + * @param n number of rows (and columns) + */ + private void assignUnitMatrix(int n) + { + numRows = n; + numColumns = n; + length = (n + 31) >>> 5; + matrix = new int[numRows][length]; + for (int i = 0; i < numRows; i++) + { + for (int j = 0; j < length; j++) + { + matrix[i][j] = 0; + } + } + for (int i = 0; i < numRows; i++) + { + int rest = i & 0x1f; + matrix[i][i >>> 5] = 1 << rest; + } + } + + /** + * Create a nxn random lower triangular matrix. + * + * @param n number of rows (and columns) + * @param sr source of randomness + */ + private void assignRandomLowerTriangularMatrix(int n, SecureRandom sr) + { + numRows = n; + numColumns = n; + length = (n + 31) >>> 5; + matrix = new int[numRows][length]; + for (int i = 0; i < numRows; i++) + { + int q = i >>> 5; + int r = i & 0x1f; + int s = 31 - r; + r = 1 << r; + for (int j = 0; j < q; j++) + { + matrix[i][j] = sr.nextInt(); + } + matrix[i][q] = (sr.nextInt() >>> s) | r; + for (int j = q + 1; j < length; j++) + { + matrix[i][j] = 0; + } + + } + + } + + /** + * Create a nxn random upper triangular matrix. + * + * @param n number of rows (and columns) + * @param sr source of randomness + */ + private void assignRandomUpperTriangularMatrix(int n, SecureRandom sr) + { + numRows = n; + numColumns = n; + length = (n + 31) >>> 5; + matrix = new int[numRows][length]; + int rest = n & 0x1f; + int help; + if (rest == 0) + { + help = 0xffffffff; + } + else + { + help = (1 << rest) - 1; + } + for (int i = 0; i < numRows; i++) + { + int q = i >>> 5; + int r = i & 0x1f; + int s = r; + r = 1 << r; + for (int j = 0; j < q; j++) + { + matrix[i][j] = 0; + } + matrix[i][q] = (sr.nextInt() << s) | r; + for (int j = q + 1; j < length; j++) + { + matrix[i][j] = sr.nextInt(); + } + matrix[i][length - 1] &= help; + } + + } + + /** + * Create an nxn random regular matrix. + * + * @param n number of rows (and columns) + * @param sr source of randomness + */ + private void assignRandomRegularMatrix(int n, SecureRandom sr) + { + numRows = n; + numColumns = n; + length = (n + 31) >>> 5; + matrix = new int[numRows][length]; + GF2Matrix lm = new GF2Matrix(n, Matrix.MATRIX_TYPE_RANDOM_LT, sr); + GF2Matrix um = new GF2Matrix(n, Matrix.MATRIX_TYPE_RANDOM_UT, sr); + GF2Matrix rm = (GF2Matrix)lm.rightMultiply(um); + Permutation perm = new Permutation(n, sr); + int[] p = perm.getVector(); + for (int i = 0; i < n; i++) + { + System.arraycopy(rm.matrix[i], 0, matrix[p[i]], 0, length); + } + } + + /** + * Create a nxn random regular matrix and its inverse. + * + * @param n number of rows (and columns) + * @param sr source of randomness + * @return the created random regular matrix and its inverse + */ + public static GF2Matrix[] createRandomRegularMatrixAndItsInverse(int n, + SecureRandom sr) + { + + GF2Matrix[] result = new GF2Matrix[2]; + + // ------------------------------------ + // First part: create regular matrix + // ------------------------------------ + + // ------ + int length = (n + 31) >> 5; + GF2Matrix lm = new GF2Matrix(n, Matrix.MATRIX_TYPE_RANDOM_LT, sr); + GF2Matrix um = new GF2Matrix(n, Matrix.MATRIX_TYPE_RANDOM_UT, sr); + GF2Matrix rm = (GF2Matrix)lm.rightMultiply(um); + Permutation p = new Permutation(n, sr); + int[] pVec = p.getVector(); + + int[][] matrix = new int[n][length]; + for (int i = 0; i < n; i++) + { + System.arraycopy(rm.matrix[pVec[i]], 0, matrix[i], 0, length); + } + + result[0] = new GF2Matrix(n, matrix); + + // ------------------------------------ + // Second part: create inverse matrix + // ------------------------------------ + + // inverse to lm + GF2Matrix invLm = new GF2Matrix(n, Matrix.MATRIX_TYPE_UNIT); + for (int i = 0; i < n; i++) + { + int rest = i & 0x1f; + int q = i >>> 5; + int r = 1 << rest; + for (int j = i + 1; j < n; j++) + { + int b = (lm.matrix[j][q]) & r; + if (b != 0) + { + for (int k = 0; k <= q; k++) + { + invLm.matrix[j][k] ^= invLm.matrix[i][k]; + } + } + } + } + // inverse to um + GF2Matrix invUm = new GF2Matrix(n, Matrix.MATRIX_TYPE_UNIT); + for (int i = n - 1; i >= 0; i--) + { + int rest = i & 0x1f; + int q = i >>> 5; + int r = 1 << rest; + for (int j = i - 1; j >= 0; j--) + { + int b = (um.matrix[j][q]) & r; + if (b != 0) + { + for (int k = q; k < length; k++) + { + invUm.matrix[j][k] ^= invUm.matrix[i][k]; + } + } + } + } + + // inverse matrix + result[1] = (GF2Matrix)invUm.rightMultiply(invLm.rightMultiply(p)); + + return result; + } + + /** + * @return the array keeping the matrix elements + */ + public int[][] getIntArray() + { + return matrix; + } + + /** + * @return the length of each array representing a row of this matrix + */ + public int getLength() + { + return length; + } + + /** + * Return the row of this matrix with the given index. + * + * @param index the index + * @return the row of this matrix with the given index + */ + public int[] getRow(int index) + { + return matrix[index]; + } + + /** + * Returns encoded matrix, i.e., this matrix in byte array form + * + * @return the encoded matrix + */ + public byte[] getEncoded() + { + int n = (numColumns + 7) >>> 3; + n *= numRows; + n += 8; + byte[] enc = new byte[n]; + + LittleEndianConversions.I2OSP(numRows, enc, 0); + LittleEndianConversions.I2OSP(numColumns, enc, 4); + + // number of "full" integer + int q = numColumns >>> 5; + // number of bits in non-full integer + int r = numColumns & 0x1f; + + int count = 8; + for (int i = 0; i < numRows; i++) + { + for (int j = 0; j < q; j++, count += 4) + { + LittleEndianConversions.I2OSP(matrix[i][j], enc, count); + } + for (int j = 0; j < r; j += 8) + { + enc[count++] = (byte)((matrix[i][q] >>> j) & 0xff); + } + + } + return enc; + } + + + /** + * Returns the percentage of the number of "ones" in this matrix. + * + * @return the Hamming weight of this matrix (as a ratio). + */ + public double getHammingWeight() + { + double counter = 0.0; + double elementCounter = 0.0; + int rest = numColumns & 0x1f; + int d; + if (rest == 0) + { + d = length; + } + else + { + d = length - 1; + } + + for (int i = 0; i < numRows; i++) + { + + for (int j = 0; j < d; j++) + { + int a = matrix[i][j]; + for (int k = 0; k < 32; k++) + { + int b = (a >>> k) & 1; + counter = counter + b; + elementCounter = elementCounter + 1; + } + } + int a = matrix[i][length - 1]; + for (int k = 0; k < rest; k++) + { + int b = (a >>> k) & 1; + counter = counter + b; + elementCounter = elementCounter + 1; + } + } + + return counter / elementCounter; + } + + /** + * 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 < length; j++) + { + if (matrix[i][j] != 0) + { + return false; + } + } + } + return true; + } + + /** + * Get the quadratic submatrix of this matrix consisting of the leftmost + * <tt>numRows</tt> columns. + * + * @return the <tt>(numRows x numRows)</tt> submatrix + */ + public GF2Matrix getLeftSubMatrix() + { + if (numColumns <= numRows) + { + throw new ArithmeticException("empty submatrix"); + } + int length = (numRows + 31) >> 5; + int[][] result = new int[numRows][length]; + int bitMask = (1 << (numRows & 0x1f)) - 1; + if (bitMask == 0) + { + bitMask = -1; + } + for (int i = numRows - 1; i >= 0; i--) + { + System.arraycopy(matrix[i], 0, result[i], 0, length); + result[i][length - 1] &= bitMask; + } + return new GF2Matrix(numRows, result); + } + + /** + * Compute the full form matrix <tt>(this | Id)</tt> from this matrix in + * left compact form, where <tt>Id</tt> is the <tt>k x k</tt> identity + * matrix and <tt>k</tt> is the number of rows of this matrix. + * + * @return <tt>(this | Id)</tt> + */ + public GF2Matrix extendLeftCompactForm() + { + int newNumColumns = numColumns + numRows; + GF2Matrix result = new GF2Matrix(numRows, newNumColumns); + + int ind = numRows - 1 + numColumns; + for (int i = numRows - 1; i >= 0; i--, ind--) + { + // copy this matrix to first columns + System.arraycopy(matrix[i], 0, result.matrix[i], 0, length); + // store the identity in last columns + result.matrix[i][ind >> 5] |= 1 << (ind & 0x1f); + } + + return result; + } + + /** + * Get the submatrix of this matrix consisting of the rightmost + * <tt>numColumns-numRows</tt> columns. + * + * @return the <tt>(numRows x (numColumns-numRows))</tt> submatrix + */ + public GF2Matrix getRightSubMatrix() + { + if (numColumns <= numRows) + { + throw new ArithmeticException("empty submatrix"); + } + + int q = numRows >> 5; + int r = numRows & 0x1f; + + GF2Matrix result = new GF2Matrix(numRows, numColumns - numRows); + + for (int i = numRows - 1; i >= 0; i--) + { + // if words have to be shifted + if (r != 0) + { + int ind = q; + // process all but last word + for (int j = 0; j < result.length - 1; j++) + { + // shift to correct position + result.matrix[i][j] = (matrix[i][ind++] >>> r) + | (matrix[i][ind] << (32 - r)); + } + // process last word + result.matrix[i][result.length - 1] = matrix[i][ind++] >>> r; + if (ind < length) + { + result.matrix[i][result.length - 1] |= matrix[i][ind] << (32 - r); + } + } + else + { + // no shifting necessary + System.arraycopy(matrix[i], q, result.matrix[i], 0, + result.length); + } + } + return result; + } + + /** + * Compute the full form matrix <tt>(Id | this)</tt> from this matrix in + * right compact form, where <tt>Id</tt> is the <tt>k x k</tt> identity + * matrix and <tt>k</tt> is the number of rows of this matrix. + * + * @return <tt>(Id | this)</tt> + */ + public GF2Matrix extendRightCompactForm() + { + GF2Matrix result = new GF2Matrix(numRows, numRows + numColumns); + + int q = numRows >> 5; + int r = numRows & 0x1f; + + for (int i = numRows - 1; i >= 0; i--) + { + // store the identity in first columns + result.matrix[i][i >> 5] |= 1 << (i & 0x1f); + + // copy this matrix to last columns + + // if words have to be shifted + if (r != 0) + { + int ind = q; + // process all but last word + for (int j = 0; j < length - 1; j++) + { + // obtain matrix word + int mw = matrix[i][j]; + // shift to correct position + result.matrix[i][ind++] |= mw << r; + result.matrix[i][ind] |= mw >>> (32 - r); + } + // process last word + int mw = matrix[i][length - 1]; + result.matrix[i][ind++] |= mw << r; + if (ind < result.length) + { + result.matrix[i][ind] |= mw >>> (32 - r); + } + } + else + { + // no shifting necessary + System.arraycopy(matrix[i], 0, result.matrix[i], q, length); + } + } + + return result; + } + + /** + * Compute the transpose of this matrix. + * + * @return <tt>(this)<sup>T</sup></tt> + */ + public Matrix computeTranspose() + { + int[][] result = new int[numColumns][(numRows + 31) >>> 5]; + for (int i = 0; i < numRows; i++) + { + for (int j = 0; j < numColumns; j++) + { + int qs = j >>> 5; + int rs = j & 0x1f; + int b = (matrix[i][qs] >>> rs) & 1; + int qt = i >>> 5; + int rt = i & 0x1f; + if (b == 1) + { + result[j][qt] |= 1 << rt; + } + } + } + + return new GF2Matrix(numRows, result); + } + + /** + * Compute the inverse of this matrix. + * + * @return the inverse of this matrix (newly created). + * @throws ArithmeticException if this matrix is not invertible. + */ + public Matrix computeInverse() + { + if (numRows != numColumns) + { + throw new ArithmeticException("Matrix is not invertible."); + } + + // clone this matrix + int[][] tmpMatrix = new int[numRows][length]; + 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][length]; + for (int i = numRows - 1; i >= 0; i--) + { + int q = i >> 5; + int r = i & 0x1f; + invMatrix[i][q] = 1 << r; + } + + // simultaneously compute Gaussian reduction of tmpMatrix and unit + // matrix + for (int i = 0; i < numRows; i++) + { + // i = q * 32 + (i mod 32) + int q = i >> 5; + int bitMask = 1 << (i & 0x1f); + // if diagonal element is zero + if ((tmpMatrix[i][q] & bitMask) == 0) + { + boolean foundNonZero = false; + // find a non-zero element in the same column + for (int j = i + 1; j < numRows; j++) + { + if ((tmpMatrix[j][q] & bitMask) != 0) + { + // found it, swap rows ... + foundNonZero = true; + swapRows(tmpMatrix, i, j); + swapRows(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 all but i-th row + for (int j = numRows - 1; j >= 0; j--) + { + if ((j != i) && ((tmpMatrix[j][q] & bitMask) != 0)) + { + addToRow(tmpMatrix[i], tmpMatrix[j], q); + addToRow(invMatrix[i], invMatrix[j], 0); + } + } + } + + return new GF2Matrix(numColumns, invMatrix); + } + + /** + * Compute the product of a permutation matrix (which is generated from an + * n-permutation) and this matrix. + * + * @param p the permutation + * @return {@link GF2Matrix} <tt>P*this</tt> + */ + public Matrix leftMultiply(Permutation p) + { + int[] pVec = p.getVector(); + if (pVec.length != numRows) + { + throw new ArithmeticException("length mismatch"); + } + + int[][] result = new int[numRows][]; + + for (int i = numRows - 1; i >= 0; i--) + { + result[i] = IntUtils.clone(matrix[pVec[i]]); + } + + return new GF2Matrix(numRows, result); + } + + /** + * compute product a row vector and this matrix + * + * @param vec a vector over GF(2) + * @return Vector product a*matrix + */ + public Vector leftMultiply(Vector vec) + { + + if (!(vec instanceof GF2Vector)) + { + throw new ArithmeticException("vector is not defined over GF(2)"); + } + + if (vec.length != numRows) + { + throw new ArithmeticException("length mismatch"); + } + + int[] v = ((GF2Vector)vec).getVecArray(); + int[] res = new int[length]; + + int q = numRows >> 5; + int r = 1 << (numRows & 0x1f); + + // compute scalar products with full words of vector + int row = 0; + for (int i = 0; i < q; i++) + { + int bitMask = 1; + do + { + int b = v[i] & bitMask; + if (b != 0) + { + for (int j = 0; j < length; j++) + { + res[j] ^= matrix[row][j]; + } + } + row++; + bitMask <<= 1; + } + while (bitMask != 0); + } + + // compute scalar products with last word of vector + int bitMask = 1; + while (bitMask != r) + { + int b = v[q] & bitMask; + if (b != 0) + { + for (int j = 0; j < length; j++) + { + res[j] ^= matrix[row][j]; + } + } + row++; + bitMask <<= 1; + } + + return new GF2Vector(res, numColumns); + } + + /** + * Compute the product of the matrix <tt>(this | Id)</tt> and a column + * vector, where <tt>Id</tt> is a <tt>(numRows x numRows)</tt> unit + * matrix. + * + * @param vec the vector over GF(2) + * @return <tt>(this | Id)*vector</tt> + */ + public Vector leftMultiplyLeftCompactForm(Vector vec) + { + if (!(vec instanceof GF2Vector)) + { + throw new ArithmeticException("vector is not defined over GF(2)"); + } + + if (vec.length != numRows) + { + throw new ArithmeticException("length mismatch"); + } + + int[] v = ((GF2Vector)vec).getVecArray(); + int[] res = new int[(numRows + numColumns + 31) >>> 5]; + + // process full words of vector + int words = numRows >>> 5; + int row = 0; + for (int i = 0; i < words; i++) + { + int bitMask = 1; + do + { + int b = v[i] & bitMask; + if (b != 0) + { + // compute scalar product part + for (int j = 0; j < length; j++) + { + res[j] ^= matrix[row][j]; + } + // set last bit + int q = (numColumns + row) >>> 5; + int r = (numColumns + row) & 0x1f; + res[q] |= 1 << r; + } + row++; + bitMask <<= 1; + } + while (bitMask != 0); + } + + // process last word of vector + int rem = 1 << (numRows & 0x1f); + int bitMask = 1; + while (bitMask != rem) + { + int b = v[words] & bitMask; + if (b != 0) + { + // compute scalar product part + for (int j = 0; j < length; j++) + { + res[j] ^= matrix[row][j]; + } + // set last bit + int q = (numColumns + row) >>> 5; + int r = (numColumns + row) & 0x1f; + res[q] |= 1 << r; + } + row++; + bitMask <<= 1; + } + + return new GF2Vector(res, numRows + numColumns); + } + + /** + * Compute the product of this matrix and a matrix A over GF(2). + * + * @param mat a matrix A over GF(2) + * @return matrix product <tt>this*matrixA</tt> + */ + public Matrix rightMultiply(Matrix mat) + { + if (!(mat instanceof GF2Matrix)) + { + throw new ArithmeticException("matrix is not defined over GF(2)"); + } + + if (mat.numRows != numColumns) + { + throw new ArithmeticException("length mismatch"); + } + + GF2Matrix a = (GF2Matrix)mat; + GF2Matrix result = new GF2Matrix(numRows, mat.numColumns); + + int d; + int rest = numColumns & 0x1f; + if (rest == 0) + { + d = length; + } + else + { + d = length - 1; + } + for (int i = 0; i < numRows; i++) + { + int count = 0; + for (int j = 0; j < d; j++) + { + int e = matrix[i][j]; + for (int h = 0; h < 32; h++) + { + int b = e & (1 << h); + if (b != 0) + { + for (int g = 0; g < a.length; g++) + { + result.matrix[i][g] ^= a.matrix[count][g]; + } + } + count++; + } + } + int e = matrix[i][length - 1]; + for (int h = 0; h < rest; h++) + { + int b = e & (1 << h); + if (b != 0) + { + for (int g = 0; g < a.length; g++) + { + result.matrix[i][g] ^= a.matrix[count][g]; + } + } + count++; + } + + } + + return result; + } + + /** + * Compute the product of this matrix and a permutation matrix which is + * generated from an n-permutation. + * + * @param p the permutation + * @return {@link GF2Matrix} <tt>this*P</tt> + */ + public Matrix rightMultiply(Permutation p) + { + + int[] pVec = p.getVector(); + if (pVec.length != numColumns) + { + throw new ArithmeticException("length mismatch"); + } + + GF2Matrix result = new GF2Matrix(numRows, numColumns); + + for (int i = numColumns - 1; i >= 0; i--) + { + int q = i >>> 5; + int r = i & 0x1f; + int pq = pVec[i] >>> 5; + int pr = pVec[i] & 0x1f; + for (int j = numRows - 1; j >= 0; j--) + { + result.matrix[j][q] |= ((matrix[j][pq] >>> pr) & 1) << r; + } + } + + return result; + } + + /** + * Compute the product of this matrix and the given column vector. + * + * @param vec the vector over GF(2) + * @return <tt>this*vector</tt> + */ + public Vector rightMultiply(Vector vec) + { + if (!(vec instanceof GF2Vector)) + { + throw new ArithmeticException("vector is not defined over GF(2)"); + } + + if (vec.length != numColumns) + { + throw new ArithmeticException("length mismatch"); + } + + int[] v = ((GF2Vector)vec).getVecArray(); + int[] res = new int[(numRows + 31) >>> 5]; + + for (int i = 0; i < numRows; i++) + { + // compute full word scalar products + int help = 0; + for (int j = 0; j < length; j++) + { + help ^= matrix[i][j] & v[j]; + } + // compute single word scalar product + int bitValue = 0; + for (int j = 0; j < 32; j++) + { + bitValue ^= (help >>> j) & 1; + } + // set result bit + if (bitValue == 1) + { + res[i >>> 5] |= 1 << (i & 0x1f); + } + } + + return new GF2Vector(res, numRows); + } + + /** + * Compute the product of the matrix <tt>(Id | this)</tt> and a column + * vector, where <tt>Id</tt> is a <tt>(numRows x numRows)</tt> unit + * matrix. + * + * @param vec the vector over GF(2) + * @return <tt>(Id | this)*vector</tt> + */ + public Vector rightMultiplyRightCompactForm(Vector vec) + { + if (!(vec instanceof GF2Vector)) + { + throw new ArithmeticException("vector is not defined over GF(2)"); + } + + if (vec.length != numColumns + numRows) + { + throw new ArithmeticException("length mismatch"); + } + + int[] v = ((GF2Vector)vec).getVecArray(); + int[] res = new int[(numRows + 31) >>> 5]; + + int q = numRows >> 5; + int r = numRows & 0x1f; + + // for all rows + for (int i = 0; i < numRows; i++) + { + // get vector bit + int help = (v[i >> 5] >>> (i & 0x1f)) & 1; + + // compute full word scalar products + int vInd = q; + // if words have to be shifted + if (r != 0) + { + int vw = 0; + // process all but last word + for (int j = 0; j < length - 1; j++) + { + // shift to correct position + vw = (v[vInd++] >>> r) | (v[vInd] << (32 - r)); + help ^= matrix[i][j] & vw; + } + // process last word + vw = v[vInd++] >>> r; + if (vInd < v.length) + { + vw |= v[vInd] << (32 - r); + } + help ^= matrix[i][length - 1] & vw; + } + else + { + // no shifting necessary + for (int j = 0; j < length; j++) + { + help ^= matrix[i][j] & v[vInd++]; + } + } + + // compute single word scalar product + int bitValue = 0; + for (int j = 0; j < 32; j++) + { + bitValue ^= help & 1; + help >>>= 1; + } + + // set result bit + if (bitValue == 1) + { + res[i >> 5] |= 1 << (i & 0x1f); + } + } + + return new GF2Vector(res, numRows); + } + + /** + * Compare this matrix with another object. + * + * @param other another object + * @return the result of the comparison + */ + public boolean equals(Object other) + { + + if (!(other instanceof GF2Matrix)) + { + return false; + } + GF2Matrix otherMatrix = (GF2Matrix)other; + + if ((numRows != otherMatrix.numRows) + || (numColumns != otherMatrix.numColumns) + || (length != otherMatrix.length)) + { + return false; + } + + for (int i = 0; i < numRows; i++) + { + if (!IntUtils.equals(matrix[i], otherMatrix.matrix[i])) + { + return false; + } + } + + return true; + } + + /** + * @return the hash code of this matrix + */ + public int hashCode() + { + int hash = (numRows * 31 + numColumns) * 31 + length; + for (int i = 0; i < numRows; i++) + { + hash = hash * 31 + matrix[i].hashCode(); + } + return hash; + } + + /** + * @return a human readable form of the matrix + */ + public String toString() + { + int rest = numColumns & 0x1f; + int d; + if (rest == 0) + { + d = length; + } + else + { + d = length - 1; + } + + StringBuffer buf = new StringBuffer(); + for (int i = 0; i < numRows; i++) + { + buf.append(i + ": "); + for (int j = 0; j < d; j++) + { + int a = matrix[i][j]; + for (int k = 0; k < 32; k++) + { + int b = (a >>> k) & 1; + if (b == 0) + { + buf.append('0'); + } + else + { + buf.append('1'); + } + } + buf.append(' '); + } + int a = matrix[i][length - 1]; + for (int k = 0; k < rest; k++) + { + int b = (a >>> k) & 1; + if (b == 0) + { + buf.append('0'); + } + else + { + buf.append('1'); + } + } + buf.append('\n'); + } + + return buf.toString(); + } + + /** + * Swap two rows of the given matrix. + * + * @param matrix the matrix + * @param first the index of the first row + * @param second the index of the second row + */ + private static void swapRows(int[][] matrix, int first, int second) + { + int[] tmp = matrix[first]; + matrix[first] = matrix[second]; + matrix[second] = tmp; + } + + /** + * Partially add one row to another. + * + * @param fromRow the addend + * @param toRow the row to add to + * @param startIndex the array index to start from + */ + private static void addToRow(int[] fromRow, int[] toRow, int startIndex) + { + for (int i = toRow.length - 1; i >= startIndex; i--) + { + toRow[i] = fromRow[i] ^ toRow[i]; + } + } + +} |