NPMV-Complete Functions That Compute Discrete Logarithms and Integer Factorization
Summary :
We define two functions fDL 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 fDL, and (b) computing integer factorization reduces to fIF. These are the first complete functions that have explicit reductions from significant cryptographic primitives.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.1 pp.342-344
- Publication Date
- 2008/01/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1093/ietfec/e91-a.1.342
- Type of Manuscript
- Special Section LETTER (Special Section on Cryptography and Information Security)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shingo HASEGAWA, Shuji ISOBE, Hiroki SHIZUYA, "NPMV-Complete Functions That Compute Discrete Logarithms and Integer Factorization" in IEICE TRANSACTIONS on Fundamentals,
vol. E91-A, no. 1, pp. 342-344, January 2008, doi: 10.1093/ietfec/e91-a.1.342.
Abstract: We define two functions fDL 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 fDL, and (b) computing integer factorization reduces to fIF. These are the first complete functions that have explicit reductions from significant cryptographic primitives.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e91-a.1.342/_p
Copy
@ARTICLE{e91-a_1_342,
author={Shingo HASEGAWA, Shuji ISOBE, Hiroki SHIZUYA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={NPMV-Complete Functions That Compute Discrete Logarithms and Integer Factorization},
year={2008},
volume={E91-A},
number={1},
pages={342-344},
abstract={We define two functions fDL 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 fDL, and (b) computing integer factorization reduces to fIF. These are the first complete functions that have explicit reductions from significant cryptographic primitives.},
keywords={},
doi={10.1093/ietfec/e91-a.1.342},
ISSN={1745-1337},
month={January},}
Copy
TY - JOUR
TI - NPMV-Complete Functions That Compute Discrete Logarithms and Integer Factorization
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 342
EP - 344
AU - Shingo HASEGAWA
AU - Shuji ISOBE
AU - Hiroki SHIZUYA
PY - 2008
DO - 10.1093/ietfec/e91-a.1.342
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E91-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2008
AB - We define two functions fDL 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 fDL, and (b) computing integer factorization reduces to fIF. These are the first complete functions that have explicit reductions from significant cryptographic primitives.
ER -
English
