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.
|Number of pages||3|
|Journal||IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences|
|Publication status||Published - 2008|
- Discrete logarithm
- Integer factoring