NPMV-complete functions that compute discrete logarithms and integer factorization

Research output: Contribution to journalArticlepeer-review


We define two functions πDL and fif in NPMV, the class of all partial, multivalued functions computed nondeterministically in polynomial time. We prove that they are complete for NPMV, and show that (a) computing discrete logarithms modulo a prime reduces to fdland (b) computing integer factorization reduces to fIF. These are the first complete functions that have explicit reductions from significant cryptographic primitives.

Original languageEnglish
Pages (from-to)342-344
Number of pages3
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number1
Publication statusPublished - 2008


  • Discrete logarithm
  • Integer factoring
  • NPMV
  • NPMV-complete


Dive into the research topics of 'NPMV-complete functions that compute discrete logarithms and integer factorization'. Together they form a unique fingerprint.

Cite this