6
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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$). $\endgroup$ Feb 3 '14 at 23:49
  • $\begingroup$ $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)$. $\endgroup$ Feb 4 '14 at 16:32
  • $\begingroup$ I see what you mean. In any case the exponent can be stored modulo $\varphi(n)$, where $\varphi$ is Euler's totient function. $\endgroup$ Feb 4 '14 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.