A reduction of integer factorization to modular tetration

DOI10.1142/S0129054120500197MaRDI QIDQ5859627zbMATH OpenOpenAlexFDO

Authors Markus Hittmeir

Publication date 19 April 2021

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.04919

zbMATH Keywords

factorizationprimalitytetration

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Factorization (11Y05) Number-theoretic algorithms; complexity (11Y16)

Abstract: Let $a,kinmathbbN$. For the $k-1$-th iterate of the exponential function $xmapsto{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.

Recommendations

• On deterministic reduction of factoring integers to computing the exponents of elements in modular group
• Integer factoring and compositeness witnesses
• scientific article; zbMATH DE number 32160
• Reductions among number theoretic problems
• A deterministic algorithm for integer factorization

Cites work

• scientific article; zbMATH DE number 3116691 (Why is no real title available?)
• scientific article; zbMATH DE number 3460351 (Why is no real title available?)
• A babystep-giantstep method for faster deterministic integer factorization
• Algorithms in Algebraic Number Theory
• Even faster integer multiplication
• Faster deterministic integer factorization
• Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
• Modular arithmetic of iterated powers
• On pairs of coprime integers with no large prime factors
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Prime numbers and computer methods for factorization.
• Some results on computational complexity
• The joy of factoring

Cited in

(1)

• Reduction Mod p of Standard Bases

This page was built for publication: A reduction of integer factorization to modular tetration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5859627)