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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Sasho Nikolov
    Commented Feb 3, 2014 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$
    – Chad Brewbaker
    Commented Feb 4, 2014 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$
    – Sasho Nikolov
    Commented Feb 4, 2014 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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