Finding Inverse of an array not working via sympy inverse Python

Question

Can Someone explain why the inverse isn't working with this matrix but it is with the commented part?

from sympy import Matrix
list = []
print(self.get_key_secret())
key = np.array([7, 23, 21, 9, 19, 3, 15, 15, 12]).reshape(3, 3)
# key = np.array(
#     [[3, 10, 20],
#     [20, 9, 17],
#     [9, 4, 17]])
print(self.get_message_secret().shape)
encr = np.matmul(self.get_message_secret(), key)
encr = encr % 26
inverse_keyArray = Matrix(key).inv_mod(26)
print(inverse_keyArray)
inverse_keyArray = np.array(inverse_keyArray).astype(float)
print(inverse_keyArray)
decryption = np.matmul(encr, inverse_keyArray)
res = np.remainder(decryption, 26)
print(res)

I get the errors

ValueError: inverse of -3318 (mod 26) does not exist
sympy.matrices.common.NonInvertibleMatrixError: Matrix is not invertible (mod 26)

One of the matrices has an inverse mod 26 but the other does not. — Oscar Benjamin, Apr 24 '22 at 17:58
Don't mix `sympy` and `numpy`. You forgot to show the `print` results. — hpaulj, Apr 24 '22 at 19:57
-3318 has no inverse mod 26. Only numbers coprime to the modulus have an inverse. https://en.wikipedia.org/wiki/Modular_multiplicative_inverse has info about this. (Wikipedia is generally *not* a great place to learn mathematics, but it can be ok if you just need to revise stuff). — PM 2Ring, Apr 24 '22 at 21:04

hpaulj · Answer 1 · 2022-04-24T20:56:40.813

I was going to complain about the missing items like self.get_key_secret(), but realized that the inv just involves the key array:

In [1]: key = np.array([7, 23, 21, 9, 19, 3, 15, 15, 12]).reshape(3, 3)
In [2]: key
Out[2]: 
array([[ 7, 23, 21],
       [ 9, 19,  3],
       [15, 15, 12]])

Ane make a sympy.Matrix from that:

In [3]: Matrix(key)
Out[3]: 
⎡7   23  21⎤
⎢          ⎥
⎢9   19  3 ⎥
⎢          ⎥
⎣15  15  12⎦

The full error, with traceback. Admittedly it doesn't add a lot. In part because I'm not familiar with this mod inverse.

In [4]: Matrix(key).inv_mod(26)
-----------------------------------------------------------------------
ValueError                            Traceback (most recent call last)
File /usr/local/lib/python3.8/dist-packages/sympy/matrices/inverse.py:176, in _inv_mod(M, m)
    175 try:
--> 176     det_inv = mod_inverse(det_K, m)
    177 except ValueError:

File /usr/local/lib/python3.8/dist-packages/sympy/core/numbers.py:551, in mod_inverse(a, m)
    550 if c is None:
--> 551     raise ValueError('inverse of %s (mod %s) does not exist' % (a, m))
    552 return c

ValueError: inverse of -3318 (mod 26) does not exist

During handling of the above exception, another exception occurred:

NonInvertibleMatrixError              Traceback (most recent call last)
Input In [4], in <cell line: 1>()
----> 1 Matrix(key).inv_mod(26)

File /usr/local/lib/python3.8/dist-packages/sympy/matrices/matrices.py:2199, in MatrixBase.inv_mod(self, m)
   2198 def inv_mod(self, m):
-> 2199     return _inv_mod(self, m)

File /usr/local/lib/python3.8/dist-packages/sympy/matrices/inverse.py:178, in _inv_mod(M, m)
    176     det_inv = mod_inverse(det_K, m)
    177 except ValueError:
--> 178     raise NonInvertibleMatrixError('Matrix is not invertible (mod %d)' % m)
    180 K_adj = M.adjugate()
    181 K_inv = M.__class__(N, N,
    182         [det_inv * K_adj[i, j] % m for i in range(N) for j in range(N)])

NonInvertibleMatrixError: Matrix is not invertible (mod 26)

So this error has nothing to do with the mix of numpy and sympy, since it is working with a sympy Matrix.

The common numeric matrix inverse works:

In [6]: np.linalg.inv(key)
Out[6]: 
array([[-0.05515371, -0.01175407,  0.0994575 ],
       [ 0.01898734,  0.06962025, -0.05063291],
       [ 0.04520796, -0.07233273,  0.02230259]])

and the equivalent fractions version

In [9]: Matrix(key).inv()
Out[9]: 
⎡-61    -13     55 ⎤
⎢────   ────   ─── ⎥
⎢1106   1106   553 ⎥
⎢                  ⎥
⎢        11        ⎥
⎢3/158  ───   -4/79⎥
⎢       158        ⎥
⎢                  ⎥
⎢  25   -40    37  ⎥
⎢ ───   ────  ──── ⎥
⎣ 553   553   1659 ⎦

Trying other mod:

In [15]: Matrix(key).inv_mod(5)
Out[15]: 
⎡4  2  0⎤
⎢       ⎥
⎢1  2  4⎥
⎢       ⎥
⎣0  0  3⎦

It also works for other powers of 5.

I don't think you need to convert sympy matrix objects to numpy, since sympy handles matrix multiplication (with the same @ operator), and you are only working with 2d Matrices - you don't need the 'batch' functionality of the numpy matmul.

So for example:

In [32]: M = Matrix(key)
In [33]: M1= M.inv_mod(5)
In [34]: M@M1
Out[34]: 
⎡51  60  155⎤
⎢           ⎥
⎢55  56  85 ⎥
⎢           ⎥
⎣75  60  96 ⎦

Sticking with sympy avoids the float issues of numeric inverse.

In [38]: M@M.inv()
Out[38]: 
⎡1  0  0⎤
⎢       ⎥
⎢0  1  0⎥
⎢       ⎥
⎣0  0  1⎦

In [39]: key@np.linalg.inv(key)
Out[39]: 
array([[1.00000000e+00, 2.22044605e-16, 0.00000000e+00],
       [0.00000000e+00, 1.00000000e+00, 1.24900090e-16],
       [1.11022302e-16, 0.00000000e+00, 1.00000000e+00]])

Finding Inverse of an array not working via sympy inverse Python

1 Answers1