NPMV-complete functions that compute discrete logarithms and integer factorization

Shingo Hasegawa; Shuji Isobe; Hiroki Shizuya

doi:10.1093/ietfec/e91-a.1.342

NPMV-complete functions that compute discrete logarithms and integer factorization

Shingo Hasegawa, Shuji Isobe, Hiroki Shizuya

Research output: Contribution to journal › Article › peer-review

Abstract

We define two functions π_DL and f_if 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 f_dland (b) computing integer factorization reduces to f_IF. These are the first complete functions that have explicit reductions from significant cryptographic primitives.

Original language	English
Pages (from-to)	342-344
Number of pages	3
Journal	IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Volume	E91-A
Issue number	1
DOIs	https://doi.org/10.1093/ietfec/e91-a.1.342
Publication status	Published - 2008

Keywords

Discrete logarithm
Integer factoring
NPMV
NPMV-complete

Access to Document

10.1093/ietfec/e91-a.1.342

Cite this

@article{d967ed6e248c4ccf816bd4cb6d8e6740,

title = "NPMV-complete functions that compute discrete logarithms and integer factorization",

abstract = "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.",

keywords = "Discrete logarithm, Integer factoring, NPMV, NPMV-complete",

author = "Shingo Hasegawa and Shuji Isobe and Hiroki Shizuya",

year = "2008",

doi = "10.1093/ietfec/e91-a.1.342",

language = "English",

volume = "E91-A",

pages = "342--344",

journal = "IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences",

issn = "0916-8508",

publisher = "Maruzen Co., Ltd/Maruzen Kabushikikaisha",

number = "1",

}

TY - JOUR

T1 - NPMV-complete functions that compute discrete logarithms and integer factorization

AU - Hasegawa, Shingo

AU - Isobe, Shuji

AU - Shizuya, Hiroki

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

KW - Discrete logarithm

KW - Integer factoring

KW - NPMV

KW - NPMV-complete

UR - http://www.scopus.com/inward/record.url?scp=77951268534&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77951268534&partnerID=8YFLogxK

U2 - 10.1093/ietfec/e91-a.1.342

DO - 10.1093/ietfec/e91-a.1.342

M3 - Article

AN - SCOPUS:77951268534

SN - 0916-8508

VL - E91-A

SP - 342

EP - 344

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IS - 1

ER -

NPMV-complete functions that compute discrete logarithms and integer factorization

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this