On Wed, Jun 14, 2023 at 8:15 PM David Roe <roed.m...@gmail.com> wrote: > > Another possibility would be to change the __pow__ method for integer > matrices to not ignore the modulus argument. As a workaround you can either > use pari (as you discovered), or use an integer matrix and occasionally > reduce the coefficients.
I implemented something very close to efficiently reduction modulo integers when working over ZZ and probably it can implemented in __pow__(). check the attached file. sage: time M1f=matpowermodp(M,n,p) CPU times: user 528 ms, sys: 2.98 ms, total: 531 ms Wall time: 362 ms sage: time M1s=M1p**n CPU times: user 21.3 s, sys: 4.01 ms, total: 21.3 s Wall time: 21.4 s sage: M1s==M1f True -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAGUWgD8FPZQPJ_THJnzhiS80%3D%2BjwGZYC-%2BFoG5eXNuQQc1JNQw%40mail.gmail.com.
def matpowermodp(M,n,p): """ Author Georgi Guninski in the public domain M**n mod p M: matrix over the integers p=next_prime(2**100) n=200;l=list(range(n**2)) M=Matrix(ZZ,n,n,l) M1p=Matrix(Integers(p),n,n,l) M1f=matpowermodp(M,n,p) M1s=M1p**n M1s==M1f sage: time M1f=matpowermodp(M,n,p) CPU times: user 528 ms, sys: 2.98 ms, total: 531 ms Wall time: 362 ms sage: time M1s=M1p**n CPU times: user 21.3 s, sys: 4.01 ms, total: 21.3 s Wall time: 21.4 s sage: M1s==M1f True """ assert n>0,"n>0" R=M n=n-1 x=M N=M.nrows() while n: if n%2==1: R *= x x=x**2 n=n//2 for i in range(N): for j in range(N): R[i,j]=R[i,j]%p x[i,j]=x[i,j]%p return R