The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Peut-on trouver en temps polynomial une courbe elliptique d'un ordre donné sur un corps fini ? Cet article s'intéresse à cette question ouverte depuis 1986. Considérons la fonction multivaluée partielle qui produit une telle courbe elliptique. Nous caractérisons la difficulté de calculer cette fonction et montrons que la hiérarchie temporelle polynomiale s'effondre si assis se réduit à cette fonction par rapport à la réductibilité de Turing en temps polynomial, où sat est la fonction partielle à plusieurs valeurs qui, en entrant une formule booléenne, produit une affectation satisfaisante. Nous donnons également un problème équivalent à la question ouverte sous l’hypothèse de Riemann étendue.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Masato YAMAMICHI, Masahiro MAMBO, Hiroki SHIZUYA, "On the Complexity of Constructing an Elliptic Curve of a Given Order" in IEICE TRANSACTIONS on Fundamentals,
vol. E84-A, no. 1, pp. 140-145, January 2001, doi: .
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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e84-a_1_140/_p
Copier
@ARTICLE{e84-a_1_140,
author={Masato YAMAMICHI, Masahiro MAMBO, Hiroki SHIZUYA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Complexity of Constructing an Elliptic Curve of a Given Order},
year={2001},
volume={E84-A},
number={1},
pages={140-145},
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.},
keywords={},
doi={},
ISSN={},
month={January},}
Copier
TY - JOUR
TI - On the Complexity of Constructing an Elliptic Curve of a Given Order
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 140
EP - 145
AU - Masato YAMAMICHI
AU - Masahiro MAMBO
AU - Hiroki SHIZUYA
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E84-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2001
AB - 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.
ER -