aboutsummaryrefslogtreecommitdiffstats
path: root/libraries/spongycastle/core/src/main/java/org/spongycastle/pqc/math/linearalgebra/GF2Matrix.java
diff options
context:
space:
mode:
Diffstat (limited to 'libraries/spongycastle/core/src/main/java/org/spongycastle/pqc/math/linearalgebra/GF2Matrix.java')
-rw-r--r--libraries/spongycastle/core/src/main/java/org/spongycastle/pqc/math/linearalgebra/GF2Matrix.java1323
1 files changed, 1323 insertions, 0 deletions
diff --git a/libraries/spongycastle/core/src/main/java/org/spongycastle/pqc/math/linearalgebra/GF2Matrix.java b/libraries/spongycastle/core/src/main/java/org/spongycastle/pqc/math/linearalgebra/GF2Matrix.java
new file mode 100644
index 000000000..7e2de19e5
--- /dev/null
+++ b/libraries/spongycastle/core/src/main/java/org/spongycastle/pqc/math/linearalgebra/GF2Matrix.java
@@ -0,0 +1,1323 @@
+package org.spongycastle.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];
+ }
+ }
+
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-13 14:45:31 +0000