I am curious $3^{n^n}$ means $(3^n)^n$, right? – 2012-11-06
0
yes. you are right. – 2012-11-06
1
I'm confused. I thought $(3^n)^n$ is $3^{n^2}$. – 2012-11-06
2
Usually $3^{n^n}$ is taken to mean $3^{(n^n)}$. Now, what model of computation are you using? – 2012-11-06
0
...Deterministic Turing machine...? – 2012-11-06
0
The classic Turing machine uses base-1 notation for integers, so $3^{n^n}$ would be represented by $3^{n^n}$ ones. Is that really what you mean? – 2012-11-06
0
@RobertIsrael, As far as I know you are free to choose the representation you prefer. And speaking about computational complexity base 2 is a good and standard choice. For this matter I don't think of my computer to be something else than a *classic* – but classy ! — Turing machine. – 2012-11-06
0
If you are computing $3^{n^n}$ modulo an integer $M$ and you know it's totient function $\varphi(M)$ then you can compute $n^n$ in $O(\log n)$ multiplications $\pmod{ \varphi(M)}$ and then rise $3$ to the result in $O(\log M)$ multiplications mod $M$ finding the result in polynomial time. The problem is to find $\varphi(M)$. Some times it can be done in polynomial time (for example if $M$ is prime then $\phi(M)=M-1$), but in general if $M$ is composite finding $\varphi(M)$ is equivalent to finding the factorization of $M$. – 2012-11-06