<p><a href="https://cstheory.stackexchange.com/questions/20594/factoriality-testing-algorithms-and-their-efficiency/">Borwein's method</a> 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$. </p>

<p>I don't see what this has to do with P vs NP.  </p>

CC BY-SA 3.0
2014-02-03T23:49:00.743Z
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$).
Sasho Nikolov
CC BY-SA 3.0
2014-02-04T16:32:59.473Z
$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)$.
Chad Brewbaker
CC BY-SA 3.0
2014-02-04T16:49:41.617Z
I see what you mean. In any case the exponent can be stored modulo $\varphi(n)$, where $\varphi$ is Euler's totient function.
Sasho Nikolov
CC BY-SA 3.0
2014-02-03T15:26:17.153Z
2014-02-04T16:34:17.793Z
2017-04-13T12:32:28.167Z
Chad Brewbaker
<p>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.</p>

<p>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&gt;m&gt;0$?</p>

<cc.complexity-theory><nt.number-theory>
Complexity of factorial exponent over composite moduli
Turbo
# Complexity of factorial exponent over composite moduli

(Asked by: username_0 on 2013-12-29)

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$?

**Tags:** cc.complexity-theory, nt.number-theory

---

## 1 answers

### Answer by username_1 on 2014-02-03. Score: 1

[Borwein's method](https://cstheory.stackexchange.com/questions/20594/factoriality-testing-algorithms-and-their-efficiency/) 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.

> **Comments:**
> **username_2**: 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$).  
> **username_1**: $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)$.  
> **username_2**: I see what you mean. In any case the exponent can be stored modulo $\varphi(n)$, where $\varphi$ is Euler's totient function.  

---

