Timeline for Computational complexity of modular power towers (tetration)
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 20, 2015 at 16:41 | comment | added | Zsbán Ambrus | For others curious about this, that result about the iterated Euler phi function is given (with a short proof) in: S. Sivasankaranarayana Pillai, "On a function connected with $\phi(n)$", Bull. Amer. Math. Soc., **35*/6, p. 837–841, (1929), metadata with full text available at projecteuclid.org/euclid.bams/1183493597 | |
| Jun 20, 2015 at 15:07 | comment | added | Zsbán Ambrus | @Jeřábek: Wow, I didn't realize that the moduluses go to 1 so quickly. That's even better than I thought. | |
| Jun 20, 2015 at 7:51 | comment | added | Emil Jeřábek | For tetration, note also that the iterated Euler function $\phi^{(h)}(m)$ converges to $1$ after $\sim\log m$ iterations, and in particular, $a\uparrow\uparrow h\bmod m$ is constant (as a function of $h$) for $h\ge\log m$ or so. Thus, you won’t need more than $O(\log m)$ factorizations. One can easily generalize this to the modular Ackermann function; the argument in mathoverflow.net/a/165938 is not written with complexity in mind so the bounds are wasteful, but if you think about what really happens there, you’ll see that tetration is actually the hardest case. | |
| Jun 20, 2015 at 0:15 | comment | added | Ross Snider | Absolutely it is relevant in the case the factorization of the modulus is known. +1 :) | |
| Jun 20, 2015 at 0:09 | comment | added | Zsbán Ambrus | I think the algorithm is relevant, because it's useful for computing a modular tetration $ a\uparrow\uparrow h \mod m $ where $ h $ and $ m $ are of comparable size. You asked about tetration in the question, which is why I thought this was relevant. There could of course be a nontrivial algorithm for tetration that's significantly faster than this, in which case maybe this isn't relevant afterall, but I don't know of such an algorithm. | |
| Jun 19, 2015 at 23:58 | comment | added | Ross Snider | Thanks Zsban. I am looking for general algorithms in this case where the factorization of the modulus may not be known. That's not to say this isn't a good addition. Thank you for the write-up. | |
| Jun 19, 2015 at 23:51 | history | answered | Zsbán Ambrus | CC BY-SA 3.0 |