Revision history [back]

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...