Reductions among number theoretic problems

DOI10.1016/0890-5401(87)90030-7zbMath0622.68041OpenAlexW1982647225MaRDI QIDQ1091136

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)

Related Items (5)

The Power of Leibniz-Like Functions as Oracles ⋮ Some remarks on computing the square parts of integers ⋮ A simple bijection between σ andn⌣{0} ⋮ New Characterization of the Factor Refinement Algorithm with Applications ⋮ Deterministic factoring with oracles

Cites Work

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

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