# Given two 3 x 3 matrices M,N, what is the positive integer i such that M^i = n ?

Hi Sage friends.

Given two 3 x 3 matrices M,N over the finite field F_q, I would like to find the positive integer i such that M^i = N. I presume that is not something easy to compute to large dimensions and finite fields, but I am working with F_121, where b is a primitive integer. Is this plausible ?

Best regards, Gustavo

edit retag close merge delete

Sort by » oldest newest most voted

This is a dscrete logarithm problem, for which no general and efficient solution is known, as far as I know.

Since your search space is finite (but large : MatrixSpace(GF(121,"z"), 3, 3).cardinality() is 5559917313492231481), the set of successive powers of any of its elements is cyclic. Your problem is to find N in [M^i for i in range(1, 5559917313492231481)]

A possible brute force solution is :

def bruteforce(M, N):
if M==N: return 1
i=1
P=copy(M)
S=[M]
while True:
i+=1
P*=M
if P==N: return i
# if P in S: return None
if P in S: return -i
S+=[P]


which returns i if there is a solution or -i if M^i==M (i. e. minus the length of the cycle if no solution).

Example of use :

sage: R1=GF(121, "z")
sage: R1.inject_variables()
Defining z
sage: R2=MatrixSpace(R1, 3, 3)
sage: foo=R2.random_element() ; foo
[ 6*z + 1  6*z + 4    z + 2]
[ 5*z + 2  2*z + 2  5*z + 3]
[10*z + 6  4*z + 5 10*z + 5]
sage: bar=R2.random_element() ; bar
[5*z + 2     2*z 4*z + 8]
[7*z + 4 4*z + 9 3*z + 2]
[4*z + 3   z + 2 8*z + 7]
sage: %time gee=bruteforce(foo, bar) ; gee
CPU times: user 12.5 s, sys: 0 ns, total: 12.5 s
Wall time: 12.5 s
-14641


Meaning that the cycle of successive powers of foo, of length 14641, doesn't contain bar. And, indeed :

sage: foo^-gee==foo
True


As advertised, this "solution", like most brute-force "solutions", is probably of no practical use.

HTH, nevertheless...

more

There are a few discrete_log_*functions that can be used here and are much efficient than brute-force. See https://doc.sagemath.org/html/en/refe...

( 2022-04-12 18:49:27 +0200 )edit

Well, somehow discrete_logdoes not work - https://trac.sagemath.org/ticket/33699

( 2022-04-12 22:36:25 +0200 )edit