Let a, k is an element of N. By (1)a := a and (k)a := a(k-1a), we denote the kth iterate of the exponential function x bar right arrow a(x) evaluated at a, also known as tetration. We demonstrate how an algorithm for evaluating tetration modulo natural numbers N could be used to compute the prime factorization of N and provide heuristic arguments for the efficiency of this reduction. Additionally, we prove that the problem of computing the squarefree part of integers is deterministically polynomial-time reducible to modular tetration.
展开▼
