Solve Matrix Multiplication Equation on Quotient Polynomial Ring

asked 2024-03-18 13:47:19 +0200

updated 2024-04-14 16:07:51 +0200

FrédéricC gravatar image

How to solve matrix multiplication equation on quotient polynomial ring? my try:

## polynomial ring
K = 4
L = 4
N = 256

F = GF(8380417)
R = F['x']
S = R.quotient(x^N+1, 'x')

A = random_matrix(S, K, L, distribution='gen')

s1_coef = [ [randint(0, 2) for i in range(N+1)] for _ in range(L)]
s1 = vector([S(_) for _ in s1_coef])
t = A*s1 

A.solve_right(t) # get X for AX = Y

And I got TypeError: base ring must be an integral domain or a ring of integers mod n

edit retag flag offensive close merge delete


Your quotient ring S has divisors of zero, hence the error. In particular, division or fraction field are not well defined for S. And with no division, there is no way to solve matrix equations.

Max Alekseyev gravatar imageMax Alekseyev ( 2024-03-19 02:40:58 +0200 )edit