On the complexity of constructing an elliptic curve of a given order

被引:0
作者
Yamamichi, Masato [1 ]
Mambo, Masahiro [1 ]
Shizuya, Hiroki [1 ]
机构
[1] Department of Computer and Mathematical Sciences, Graduate School of Information Sciences, Tohoku University, Sendai-shi, 980-8576, Japan
关键词
Algorithms - Boolean functions - Computational complexity - Computational geometry - Polynomials;
D O I
暂无
中图分类号
学科分类号
摘要
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.
引用
收藏
页码:140 / 145
相关论文
empty
未找到相关数据