discrete_log() errors out for matrices over finite fields

[maxale]

Attempt to compute discrete_log(M,M) for a matrix M over a finite field results in one of two errors:

ValueError: No discrete log of ... found to base ...

or

TypeError: mutable matrices are unhashable

depending on the given matrix M.

F = GF(9,'z')
F.inject_variables()
S = MatrixSpace(F, 2, 2)

M = Matrix(F, [[z + 2,2*z],[2,z]]) # leads to "ValueError: No discrete log of ... found to base ..."
#M = Matrix(F, [[2,2*z],[2*z + 1,2*z + 1]]) # leads to "TypeError: mutable matrices are unhashable"

r = discrete_log(M,M,ord=S.cardinality()-1) # expect r = 1

CC: @yyyyx4

Component: group theory

Issue created by migration from https://trac.sagemath.org/ticket/33699

[DaveWitteMorris]

comment:2

There is more than one issue, so more than one ticket may be needed.

The first matrix M = Matrix(F, [[z + 2,2*z],[2,z]]) reveals a bug in the code. The documentation says that ord needs to be a multiple of the order of base, but I think the code actually assumes that it is equal to base.order(). (More precisely, I think the algorithm requires that ord/base.order() is relatively prime to base.order(), but ord/base.order() does not actually need to be 1.) This bug in the code should be fixed (perhaps by searching through the factors of ord to find the order of base.order()).

sage: F = GF(9,'z')
sage: F.inject_variables()
Defining z
sage: M = Matrix(F, [[z + 2,2*z],[2,z]])
sage: M^8  # the multiplicative order of M is 8
[1 0]
[0 1]
sage: discrete_log(M, M, ord=8)  # this works
1
sage: discrete_log(M, M, ord=16)  # this does not work
    ...
ValueError: no discrete log of [z + 2   2*z]
[    2     z] found to base [z + 2   2*z]
[    2     z]

The second example in the ticket description is user error, because S.cardinality()-1 is not a valid value for ord:

sage: S = MatrixSpace(F, 2, 2)
sage: M = Matrix(F, [[2,2*z],[2*z + 1,2*z + 1]])
sage: M^(S.cardinality() - 1)  # this needs to be the identity matrix, but it's not
[  z + 1       1]
[2*z + 2 2*z + 1]

However, this example does reveal two problems in the code:

1. The function should give a better error message when the value of ord is invalid.
2. The algorithm assumes that elements of the group are hashable (because it uses a dictionary), but this is not specified in the documentation. Either this requirement needs to be documented (and a better error message issued), or an implementation needs to be provided for the unhashable case.

Another possible issue is the use of except Exception in the code. Should there be a more specific list of exceptions?