On the Complexity of Constructing an Elliptic Curve of a Given Order : Special Section on Cryptography and Information Security

スポンサーリンク

概要

• 論文の詳細を見る

• Can we find in polynomial time an elliptic curve of a given order over a finite field? This paper is concerned with this question which is open since 1986. Consider the partial multivalued function that outputs such an elliptic curve. We characterize the difficulty of computing this function, and show that the polynomial time hierarchy collapses if sat reduces to this function with respect to the polynomial time Turing reducibility, where sat is the partial multivalued function that on input a Boolean formula, outputs a satisfying assignment. We also give a problem that is equivalent to the open question under the Extended Riemann Hypothesis.

• 社団法人電子情報通信学会の論文
• 2001-01-01

著者

• Shizuya Hiroki

  The Authors Are With The Department Of Computer And Mathematical Sciences The Graduate School Of Inf

• Shizuya Hiroki

  The Author Is With Education Center For Information Processing Tohoku University

• Mambo Masahiro

  The Authors Are With The Department Of Computer And Mathematical Sciences The Graduate School Of Inf

• YAMAMICHI Masato

  The authors are with the Department of Computer and Mathematical Sciences, the Graduate School of In

• Yamamichi Masato

  The Authors Are With The Department Of Computer And Mathematical Sciences The Graduate School Of Inf

関連論文

• On the Average Length of Secret Key Exchange Eulerian Circuits(Special Section on Discrete Mathematics and Its Applications)
• A Way of Making Trapdoor One-Way Functions Trapdoor No-Way : Special Section on Cryptography and Information Security
• On the Complexity of Constructing an Elliptic Curve of a Given Order : Special Section on Cryptography and Information Security
• On the Security of the Okamoto-Tanaka ID-Based Key Exchange Scheme against Active Attacks : Special Section on Cryptography and Information Security

スポンサーリンク