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
유한한 장에 대해 주어진 차수의 타원 곡선을 다항식 시간에 찾을 수 있습니까? 본 논문은 1986년부터 공개된 이 질문에 관한 것입니다. 그러한 타원 곡선을 출력하는 부분 다중값 함수를 고려하십시오. 우리는 이 함수를 계산하는 것의 어려움을 특징으로 하고 다음과 같은 경우 다항식 시간 계층이 붕괴된다는 것을 보여줍니다. 마을 다항식 시간 Turing 환원성과 관련하여 이 함수로 감소합니다. 여기서 sat는 부울 공식 입력 시 만족스러운 할당을 출력하는 부분 다중값 함수입니다. 우리는 또한 확장된 리만 가설 하의 공개 질문과 동일한 문제를 제시합니다.
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.
부
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
부
@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},}
부
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 -