The "convert to binary" is a standard algorithm for modular exponentiation. Anyone who has taken a cryptography course will know it.

It's not the fastest algorithm (by big-O; probably is in practice), though. You can do a matrix decomposition, exponentiate the eigenvalues, and convert back. Speed will depend on how you do the exponentiation, and that's gets into a pile of optimized numerical methods.