  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.
