# Complexity of factorial exponent over composite moduli

I know that computing factorial modulo a composite number has no fast algorithm and showing non-polylogarithmic lower bound in BSS model for factorial would separate P from NP in that model.

Given $a\in\Bbb Z/n\Bbb Z$, where $n$ is composite, what is the complexity of calculating $a^{m!}$ in $\Bbb Z/n\Bbb Z$ for any given integer $n>m>0$?

## 1 Answer

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.

• computing $m!$ explicitly will take $\Omega(m)$ time, which is exponential in the input size (assuming the input is $a$, $m$ and $n$). i don't understand your remark about bucketing into counters, but remember that in general $a^p \bmod n \neq a^{p\ \bmod\ n} \bmod n$ (e.g. $a = 2$, $p = 3$, $n = 3$). Feb 3 '14 at 23:49
• $a$ is restricted to the monogenic transformation semigroup generated by itself. It follows a path then forms a cycle, so you only need a log(n) counter to store where it ends up at. I agree that Borwein's method would be "exponential" with regards to $log(m)$. Feb 4 '14 at 16:32
• I see what you mean. In any case the exponent can be stored modulo $\varphi(n)$, where $\varphi$ is Euler's totient function. Feb 4 '14 at 16:49