La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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

On the Complexity of Constructing an Elliptic Curve of a Given Order Sur la complexité de construire une courbe elliptique d'un ordre donné

Masato YAMAMICHI, Masahiro MAMBO, Hiroki SHIZUYA

  • Vues en texte intégral

    0

  • Citer

Résumé:

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.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.1 pp.140-145
Date de publication
2001/01/01
Publicisé
ISSN en ligne
DOI
Type de manuscrit
Special Section PAPER (Special Section on Cryptography and Information Security)
Catégories

Auteurs

Mots-clés

Table des matières