Let $a,k\in\mathbb{ N}$. For the $k-1$-th iterate of the exponential function $x\mapsto a^x$, also known as tetration, we write \[ ^k a:=a^{ a^{ .^{ .^{ .^{ a}}}}}. \] In this paper, we show how an efficient algorithm for tetration modulo natural numbers $N$ may be used to compute the prime factorization of $N$. In particular, we prove that the problem of computing the squarefree part of integers is deterministically polynomial-time reducible to modular tetration.
Categories: math.NT