Complexity of factorial exponent over composite moduli
Borwein's method to compute the exponent and the doubling method for multiplying out the $a$'s wouldn't be too terrible, but as @SashoNikolov pointed out it is exponential with regards to the input size. You can store all intermediate results in $O(log(n))$ bits when multiplying out $a$. 

I don't see what this has to do with P vs NP.