Reductions among number theoretic problems

DOI10.1016/0890-5401(87)90030-7MaRDI QIDQ1091136zbMATH OpenOpenAlexFDO

Authors Heather Woll

Publication date 1987

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(87)90030-7

zbMATH Keywords

deterministic polynomial time reductiondiscrete logarithminteger factorizationnumber theoretic complexitynumber theoretic problemsprobabilistic polynomial time reductionsquarefreeness

Mathematics Subject Classification ID

Primes (11A41) Radix representation; digital problems (11A63) Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60)

Review text

Many number theoretic problems such as integer factorization and the discrete logarithm problem have defined all attempts to classify their complexities. Thirteen such problems are considered, none of which is known either to have a deterministic polynomial time solution, or to be complete for any natural complexity class. Failing this, the next best goal is to determine which among these are the easiest and which are the hardest problems. Toward this end, this paper gives an overview of reductions among the problems. Two reductions are new: a deterministic polynomial time reduction from squarefreeness to Euler's function \(\phi\) (n), and a probabilistic polynomial time reduction from order modulo a prime power to discrete logarithm modulo a prime power.

Recommendations

• Reductions of algebraic integers
• Multiplicities and Reduction Numbers
• Reducibility among combinatorial problems
• Reducibility among combinatorial problems
• On p-reducibility of numerations
• scientific article; zbMATH DE number 3719211
• scientific article; zbMATH DE number 1121767
• scientific article; zbMATH DE number 3972937
• Reduction of unknowns in diophantine representations

Cites work

• A method for obtaining digital signatures and public-key cryptosystems
• A Method of Factoring and the Factorization of F 7
• A Simple Unpredictable Pseudo-Random Number Generator
• Asymptotically Fast Factorization of Integers
• Erratum: A Fast Monte-Carlo Test for Primality
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 3732172 (Why is no real title available?)
• scientific article; zbMATH DE number 3573943 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Probabilistic algorithm for testing primality
• Riemann's hypothesis and tests for primality

Cited in

(13)

• Some remarks on computing the square parts of integers
• Integer factoring and compositeness witnesses
• A simple bijection between σ andn⌣{0}
• On reducing factorization to the discrete logarithm problem modulo a composite
• Asymptotic behavior of reduction numbers
• Large sieve, Miller-Rabin compositeness witnesses and integer factoring problem
• Reductions of the Main Conjecture
• The Power of Leibniz-Like Functions as Oracles
• \texttt{NP}-complete sets for computing discrete logarithms and integer factorization
• A reduction of integer factorization to modular tetration
• New Characterization of the Factor Refinement Algorithm with Applications
• Deterministic factoring with oracles
• Integer factoring and modular square roots

This page was built for publication: Reductions among number theoretic problems

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