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

discrete logarithminteger factorizationdeterministic polynomial time reductionnumber theoretic complexitynumber theoretic problemsprobabilistic polynomial time reductionsquarefreeness

Mathematics Subject Classification ID

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

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

• 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?)
• A Method of Factoring and the Factorization of F 7
• A Simple Unpredictable Pseudo-Random Number Generator
• A method for obtaining digital signatures and public-key cryptosystems
• Asymptotically Fast Factorization of Integers
• Erratum: A Fast Monte-Carlo Test for Primality
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Probabilistic algorithm for testing primality
• Riemann's hypothesis and tests for primality

Cited in

(13)

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

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)