What are the constraints for a, n, and m?

If a and n are small, and gcd(a, m) = 1 (a & m are coprime)

Then first, remember that where φ(m) is the euler totient function of m. That means, we can simplify to

You can calculate φ(m) in O(sqrt(m)) and then calculate in O(n) and then the power with binary exponentiation in O(log₂(m)) so the total complexity is O(sqrt(m) + n + log₂(m))