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

Masato Yamamichi, Masahiro Mambo, Hiroki Shizuya

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)140-145
Number of pages6
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
VolumeE84-A
Issue number1
Publication statusPublished - 2001 Jan

Fingerprint

Dive into the research topics of 'On the complexity of constructing an elliptic curve of a given order'. Together they form a unique fingerprint.

Cite this