A Reduction of Integer Factorization to Modular Tetration
A Reduction of Integer Factorization to Modular Tetration
复制标题
整数因式分解到模四分解
DOI：
10.1142/s0129054120500197
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Markus Hittmeir
中科院分区：
文献类型：
--
作者：
Markus Hittmeir
让[公式：见正文]。通过[公式：请参阅文本]和[公式：请参阅文本]，我们表示在[公式：请参阅文本]处求值的指数函数[公式：请参阅文本]的第[公式：请参阅文本] 次迭代，也称为剖分。我们演示了如何使用计算模自然数[公式：参见文本]的算法来计算[公式：参见文本]的素因式分解，并为这种简化的效率提供了启发式的论证。此外，我们还证明了计算整数的无平方部分的问题是确定的多项式时间可约化为模三角剖分。
Let [Formula: see text]. By [Formula: see text] and [Formula: see text], we denote the [Formula: see text] th iterate of the exponential function [Formula: see text] evaluated at [Formula: see text], also known as tetration. We demonstrate how an algorithm for evaluating tetration modulo natural numbers [Formula: see text] could be used to compute the prime factorization of [Formula: see text] 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.