Is it possible to compute the factorial of a number with a bounded number of exponentiations?

Question

We can easily compute the summation of a number N, i.e., 1 + 2 + 3 + 4 + ... + N, with a bounded number of multiplications (sum(n) = n * (n + 1) * 0.5). Is it, equivalently, possible to compute the factorial of a number N, i.e., 1 * 2 * 3 * 4 * ... * N, with a bounded number of exponentiations?

Answer 1

There is no known method to do so. If we had an exact, efficient way to compute $n!$, then we could easily factor any number by just binary searching for factors using Euclid's algorithm.

Specifically, if we wanted to factor a number, $N=pq$, where $p$ and $q$ are large primes, then we could just compute $\text{gcd} (N,k!)$, as we binary search for $k$. We know $k$ is too low if $\text{gcd} (N,k!) =1$, and we know it's too high if $\text{gcd} (N,k!) =N$. Using these two "comparison metrics" we could easily find one of the factors.

However, RSA, a popular security system, relies on the fact that it is computationally impossible to factor numbers of the form $N=pq$. So if you can't break RSA, then you can't quickly compute factorials.

Additionally, if you're looking for an approximation $n! \approx \left( \frac{n}{e} \right) ^n \sqrt{2\pi n}$ is pretty good (this is Stirling's approximation).