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

Efficient Supersingularity Testing of Elliptic Curves Using Legendre Curves Test efficace de supersingularité des courbes elliptiques à l'aide des courbes de Legendre

Yuji HASHIMOTO, Koji NUIDA

  • Vues en texte intégral

    0

  • Citer

Résumé:

Il existe deux types de courbes elliptiques, les courbes elliptiques ordinaires et les courbes elliptiques supersingulières. En 2012, Sutherland a proposé un algorithme efficace et presque déterministe pour déterminer si une courbe donnée est ordinaire ou supersingulière. L'algorithme de Sutherland est basé sur des séquences d'isogénies démarrées à partir de la courbe d'entrée, et le calcul de chaque isogénie nécessite des calculs de racine carrée, ce qui constitue le coût dominant de l'algorithme. Dans cet article, nous réduisons ce coût dominant de l'algorithme de Sutherland à environ la moitié de celui d'origine. Contrairement à l'algorithme de Sutherland utilisant j-invariants et polynômes modulaires, notre algorithme proposé est basé sur la forme Legendre des courbes elliptiques, ce qui simplifie l'expression de chaque isogénie. De plus, en sélectionnant soigneusement le type d'isogénies à calculer, nous avons réussi à rassembler les calculs de racine carrée à deux étapes consécutives de l'algorithme de Sutherland en un seul calcul de quatrième racine (avec expérimentalement presque le même coût qu'un seul calcul de racine carrée). Les résultats de nos expériences utilisant Magma soutiennent notre argument ; pour les cas de caractéristique p de longueurs de 768 bits à 1024 bits, notre algorithme proposé pour les caractéristiques p≡1 (mod 4) s'exécute dans environ 61.5 % du temps et pour la caractéristique p≡3 (mod 4) s'exécute également dans environ 54.9 % du temps par rapport à l'algorithme de Sutherland.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.9 pp.1119-1130
Date de publication
2023/09/01
Publicisé
2023/03/07
ISSN en ligne
1745-1337
DOI
10.1587/transfun.2022DMP0002
Type de manuscrit
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Catégories
Cryptographie et sécurité de l'information

Auteurs

Yuji HASHIMOTO
  Tokyo Denki University,National Institute of Advanced Industrial Science and Technology
Koji NUIDA
  National Institute of Advanced Industrial Science and Technology,Kyushu University

Mots-clés

Table des matières