Instantly share code, notes, and snippets.

# StuartGordonReid/BinaryMatrix.py

Created August 25, 2015 15:59
Star You must be signed in to star a gist
A Python class for computing the rank of a binary matrix. This is used by the Binary Matrix Rank cryptographic test for randomness
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 class BinaryMatrix: def __init__(self, matrix, rows, cols): """ This class contains the algorithm specified in the NIST suite for computing the **binary rank** of a matrix. :param matrix: the matrix we want to compute the rank for :param rows: the number of rows :param cols: the number of columns :return: a BinaryMatrix object """ self.M = rows self.Q = cols self.A = matrix self.m = min(rows, cols) def compute_rank(self, verbose=False): """ This method computes the binary rank of self.matrix :param verbose: if this is true it prints out the matrix after the forward elimination and backward elimination operations on the rows. This was used to testing the method to check it is working as expected. :return: the rank of the matrix. """ if verbose: print("Original Matrix\n", self.A) i = 0 while i < self.m - 1: if self.A[i][i] == 1: self.perform_row_operations(i, True) else: found = self.find_unit_element_swap(i, True) if found == 1: self.perform_row_operations(i, True) i += 1 if verbose: print("Intermediate Matrix\n", self.A) i = self.m - 1 while i > 0: if self.A[i][i] == 1: self.perform_row_operations(i, False) else: if self.find_unit_element_swap(i, False) == 1: self.perform_row_operations(i, False) i -= 1 if verbose: print("Final Matrix\n", self.A) return self.determine_rank() def perform_row_operations(self, i, forward_elimination): """ This method performs the elementary row operations. This involves xor'ing up to two rows together depending on whether or not certain elements in the matrix contain 1's if the "current" element does not. :param i: the current index we are are looking at :param forward_elimination: True or False. """ if forward_elimination: j = i + 1 while j < self.M: if self.A[j][i] == 1: self.A[j, :] = (self.A[j, :] + self.A[i, :]) % 2 j += 1 else: j = i - 1 while j >= 0: if self.A[j][i] == 1: self.A[j, :] = (self.A[j, :] + self.A[i, :]) % 2 j -= 1 def find_unit_element_swap(self, i, forward_elimination): """ This given an index which does not contain a 1 this searches through the rows below the index to see which rows contain 1's, if they do then they swapped. This is done on the forward and backward elimination :param i: the current index we are looking at :param forward_elimination: True or False. """ row_op = 0 if forward_elimination: index = i + 1 while index < self.M and self.A[index][i] == 0: index += 1 if index < self.M: row_op = self.swap_rows(i, index) else: index = i - 1 while index >= 0 and self.A[index][i] == 0: index -= 1 if index >= 0: row_op = self.swap_rows(i, index) return row_op def swap_rows(self, i, ix): """ This method just swaps two rows in a matrix. Had to use the copy package to ensure no memory leakage :param i: the first row we want to swap and :param ix: the row we want to swap it with :return: 1 """ temp = copy.copy(self.A[i, :]) self.A[i, :] = self.A[ix, :] self.A[ix, :] = temp return 1 def determine_rank(self): """ This method determines the rank of the transformed matrix :return: the rank of the transformed matrix """ rank = self.m i = 0 while i < self.M: all_zeros = 1 for j in range(self.Q): if self.A[i][j] == 1: all_zeros = 0 if all_zeros == 1: rank -= 1 i += 1 return rank

### igiloh commented Feb 16, 2017

I'm quite convinced there are two bugs:

1. I've used this code (thanks, BTW!) and got an almost diagonal matrix - but the first and last rows were sometimes incorrect (mostly all zeros).
I have then changed the` perform_row_operations()` method, so the first `while` condition is `while i <= self.m - 1` (instead of `<`), and the second while is `>= 0`.
I then got much better results, and the output matrix was always diagonal.

2. The `determine_rank()` method returns an incorrect result in case of a matrix where self.M > self.Q (rows > cols).
To fix this, change the while condition to `while i < self.m` instead of `self.M`.

### iddo10 commented Apr 24, 2020 • edited

i have no idea why this code is so long -
here is my code for finding the rank of a matrix over GF(2):

``````def rankMat(A):
n=len(A[0])
rank = 0
for col in range(n):
j=0
rows = []
while j<len(A):
if A[j][col] == 1:
rows += [j]
j+=1
if len(rows) >= 1:
for c in range(1,len(rows)):
for k in range(n):
A[rows[c]][k] = (A[rows[c]][k] + A[rows[0]][k])%2
A.pop(rows[0])
rank += 1
for row in A:
if sum(row)>0:
rank += 1
return rank
``````