A reduction of integer factorization to modular tetration

DOI10.1142/S0129054120500197zbMATH Open1472.11312arXiv1707.04919OpenAlexW3098845467MaRDI QIDQ5859627FDOQ5859627

Authors: Markus Hittmeir 

Publication date: 19 April 2021

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

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.

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

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

zbMATH Keywords

factorizationprimalitytetration

Mathematics Subject Classification ID

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

Cites Work

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Title not available (Why is that?)
• Title not available (Why is that?)
• Faster deterministic integer factorization
• Even faster integer multiplication
• Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
• Algorithms in Algebraic Number Theory
• Prime numbers and computer methods for factorization.
• Some results on computational complexity
• Modular arithmetic of iterated powers
• On pairs of coprime integers with no large prime factors
• A babystep-giantstep method for faster deterministic integer factorization
• 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)