Python : Modulus operator giving incorrect result

Question

I am fairly new to Python and I am trying to implement the Hill Cipher as a small project. I think I have the logic figured out and have got the encryption part to work, however, in the decryption part, I am facing troubles. Especially with the modulus operator. In the decrypt function below, the second from last line is what is giving troubles.

import numpy as np
import fractions as fr

def decrypt(matrix, words):
    matrix=np.asmatrix(matrix)
    length = len(matrix)
    det_matrix=int(round((np.linalg.det(matrix))%26))
    mult_inv=(abs(det_matrix*26)/fr.gcd(det_matrix,26))/26
    matrix_inv=(((np.linalg.inv(matrix)*np.linalg.det(matrix))%26)*mult_inv)%26
    words = words.lower()
    arr = np.array([ord(i) - ord('a') for i in words], dtype=int)
    decrypt_matrix=(np.asmatrix(matrix_inv)*(np.asmatrix(arr).transpose()))%26
    return decrypt_matrix

My input to the decrypt function is:

>>> matrix
[[6, 24, 1], [13, 16, 10], [20, 17, 15]]
>>> words
'poh'

and after the calculation of det_matrix, mult_inv variable will have the value 25. So the line of code that calculates matrix_inv will have the below value, (which is absolutely correct):

>>> matrix_inv
array([[  8.,   5.,  10.],
  [ 21.,   8.,  21.],
  [ 21.,  12.,   8.]])

The array arr will have the value:

>>> arr
array([15, 14,  7])

The problem now is the next line of code, before performing the modulus the result of the expression

matrix_inv*(np.asmatrix(arr).transpose())

is:

matrix([[ 260.],
   [ 574.],
   [ 539.]])

And now, if I perform modulus 26 on the above matrix, I should get the output as

([[0.],[2.],[19.]])

However, below is what I get when I execute the expression

>>> (np.asmatrix(matrix_inv)*(np.asmatrix(arr).transpose()))%26
matrix([[ 26.],
     [  2.],
     [ 19.]])

I don't understand why the first element has been calculated incorrectly (260%26 is 0 and not 26)! However, the remaining two elements have been computed correctly!

Any help on this is much appreciated!!

P.S : I have tried running the code on versions 2.7.11 and 3.6.1. Does not work on either.

hiro protagonist · Accepted Answer

the problem is that det is a numpy.float64. what you are getting could be something like:

round(259.6 % 26) # -> round(25.600000000000023) -> 26.0

this works:

round(259.6) % 26  # 0

in your decrypted result you have:

dec = decrypt(matrix, words)
dec[0,0]      # 25.999999999989768
dec[0,0] % 26 # 25.999999999989768

it will just be displayed as 26.

as i was interested in having a modular inverse for 3x3 matrices, i wrote some code... maybe this is useful for you...

import numpy as np
from itertools import product, cycle


def gcd_xy(a, b):
    '''
    extended euclidean algo: return (g, x, y): g = gcd(a, b); a*x + b*y = d.
    '''
    q, r = divmod(a, b)
    x, y, x1, y1 = 0, 1, 1, 0
    while r != 0:
        x1, y1, x, y = x, y, x1 - q*x, y1 - q*y
        b, (q, r) = r, divmod(b, r)
    return b, x, y


def mod_inv(e, n):
    '''
    return d == 1/e mod n or raise ValueError if e and n are not co-prime.
    '''
    g, d, _ = gcd_xy(e, n)
    if g != 1:
        msg = '{} has no inverse mod {}'.format(e, n)
        raise ValueError(msg)
    d %= n
    return d


def mod_inv_matrix(matrix, n):
    '''
    modular inverse of 3x3 matrix 
    '''

    inv = np.zeros((3, 3), dtype=int)

    det = round(np.linalg.det(matrix))
    det_inv = mod_inv(det, n)

    matrixT = matrix.T
    for (i, j), sign in zip(product(range(3), repeat=2), cycle((1, -1))):
        m = np.delete(np.delete(matrixT, i, axis=0), j, axis=1)
        inv[i, j] = sign * det_inv * round(np.linalg.det(m)) % n
    return inv


def hill_decrypt(matrix, words):

    matrix_inv = mod_inv_matrix(matrix, n=26)

    words = words.lower()
    arr = np.array([ord(i) - ord('a') for i in words], dtype=int)

    plain = (matrix_inv @ arr) % 26

    return plain

matrix = np.array([[6, 24, 1], [13, 16, 10], [20, 17, 15]], dtype=int)
words = 'poh'
dec = hill_decrypt(matrix, words)
print(dec)

for the modular inverse you could also just use the gmpy module

import gmpy
gmpy.invert(7, 26)

Python : Modulus operator giving incorrect result

Answers (2)

Related Questions