Ask Your Question
1

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

asked 2022-04-11 21:51:43 +0200

gtbastos gravatar image

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 flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
0

answered 2022-04-12 17:12:09 +0200

Emmanuel Charpentier gravatar image

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

edit flag offensive delete link more

Comments

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

Max Alekseyev gravatar imageMax Alekseyev ( 2022-04-12 18:49:27 +0200 )edit

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

Max Alekseyev gravatar imageMax Alekseyev ( 2022-04-12 22:36:25 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2022-04-11 21:51:17 +0200

Seen: 49 times

Last updated: Apr 12