### Speeding up matrix multiplication?

I'm currently trying write code to compute with overconvergent modular symbols. In iterating a Hecke operator, the key (i.e. most time consuming) operation that is performed tons of times is simply taking the product of a large dense matrix say $M$ with a ~~vector, ~~vector $v$, both with integral entries. ~~The ~~

More precisely, let $p$ be a (relatively small) prime (think $p=11$) and $N$ some integer (think 100). I have an $N$ by $N$ matrix ~~is say 100 ~~and am interested in quickly computing the product $M \cdot v$ modulo $p^N$.

I am simply using the intrinsic SAGE command of multiplying a matrix by ~~100 ~~a vector, and ~~the entries are on the order of $10^{100}$. ~~I was surprised to see that working with matrices over ${\bf Z}/p^n{\bf Z}$ was much (i.e. 10 times) slower than working with matrices over ${\bf Z}$.

~~Is ~~My question: is there ~~any ~~a faster way to do this computation than using SAGE's intrinsic matrix times a vector ~~command?~~command over ${\bf Z}$?