i know about Fermat theorem it says a^phi(n) is = 1 mod(n) so if we are given, a^k mod(n), we can reduce it to a^(k mod( phi(n) ) ) mod(n). right ? we still have to take the number mudulo n(and not phi(n)) after exponentiation right ?
so first. it reduces the exponent which seems to be an optimization as we are already doing binary exponentiation.
second, does this hold for matrix as well, as we know the equation holds only if a belongs to multiplicative modulo group of n, that is, if they are co-prime, so how can we say a matrix is co-prime to a number ? links are welcome too. 