On the Complexity of Constructing an Elliptic Curve of a Given Order

Masato YAMAMICHI  Masahiro MAMBO  Hiroki SHIZUYA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E84-A   No.1   pp.140-145
Publication Date: 2001/01/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: 
Keyword: 
elliptic curve,  function class,  computational complexity,  

Full Text: PDF(215.8KB)>>
Buy this Article




Summary: 
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.