Skip to content

Instantly share code, notes, and snippets.

@StuartGordonReid
Created August 25, 2015 15:59
Show Gist options
  • Save StuartGordonReid/eb59113cb29e529b8105 to your computer and use it in GitHub Desktop.
Save StuartGordonReid/eb59113cb29e529b8105 to your computer and use it in GitHub Desktop.
A Python class for computing the rank of a binary matrix. This is used by the Binary Matrix Rank cryptographic test for randomness
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
Copy link

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
Copy link

iddo10 commented Apr 24, 2020

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment