Is this documented in the sqrt decomposition page? (BTW should be renamed square root to make it easier to search) I saw it in a Project Euler post but probably saw it elsewhere too.

Compute queries a^b mod m in O(1) time after O(sqrt m) preprocessing. It is only a factor of O(sqrt m) better than binary exponentiation but it's a nice idea of time-space tradeoff.

The idea is b only needs to be calculated mod phi(m), then let s = floor sqrt m. Precompute two arrays: a^0, a^1, ... a^s and a^s, a^2s, ... up to a^m. The idea is sqrt m is the balance point for an exponentiation.