NPMV-Complete Functions That Compute Discrete Logarithms and Integer Factorization

スポンサーリンク

概要

• 論文の詳細を見る

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

• （社）電子情報通信学会の論文
• 2008-01-01

著者

• Isobe Shuji

  Department Of Computer And Mathematical Sciences The Graduate School Of Information Sciences Tohoku

• Isobe Shuji

  Department Of Computer And Mathematical Sciences Graduate School Of Information Sciences Tohoku Univ

• HASEGAWA Shingo

  Department of Computer and Mathematical Sciences, Graduate School of Information Sciences, Tohoku Un

• SHIZUYA Hiroki

  Department of Computer and Mathematical Sciences, Graduate School of Information Sciences, Tohoku Un

• Shizuya Hiroki

  Department Of Computer And Mathematical Sciences Graduate School Of Information Sciences Tohoku Univ

• Hasegawa Shingo

  Department Of Computer And Mathematical Sciences Graduate School Of Information Sciences Tohoku Univ

• Shizuya Hiroki

  Department Of Computer And Mathematical Sciences Graduate School Of Information Sciences Tohoku Univ

関連論文

• NPMV-Complete Functions That Compute Discrete Logarithms and Integer Factorization
• On the Difficulty of Searching for a String without Decryption (Special Section on Cryptography and Information Security)
• Making Cryptographic Primitives Harder
• Toward Separating Integer Factoring from Discrete Logarithm mod p(Foundations,Cryptography and Information Security)
• On the Polynomial Time Computability of Abstract Ray-Tracing Problems(Discrete Mathematics and Its Applications)
• Gastrointestinal Stromal Tumor with Two Genetic Abnormalities on Different Alleles : Report of a Case
• On the Length-Decreasing Self-Reducibility and the Many-One-Like Reducibilities for Partial Multivalued Functions
• On the Length-Decreasing Self-Reducibility and the Many-One-Like Reducibilities for Partial Multivalued Functions

スポンサーリンク