A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

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 Teste eficiente de supersingularidade de curvas elípticas usando curvas de Legendre

Yuji HASHIMOTO, Koji NUIDA

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Existem dois tipos de curvas elípticas, curvas elípticas comuns e curvas elípticas supersingulares. Em 2012, Sutherland propôs um algoritmo eficiente e quase determinístico para determinar se uma determinada curva é ordinária ou supersingular. O algoritmo de Sutherland é baseado em sequências de isogenias iniciadas a partir da curva de entrada, e o cálculo de cada isogenia requer cálculos de raiz quadrada, que é o custo dominante do algoritmo. Neste artigo, reduzimos esse custo dominante do algoritmo de Sutherland para aproximadamente metade do original. Em contraste com o algoritmo de Sutherland usando j-invariantes e polinômios modulares, nosso algoritmo proposto é baseado na forma de curvas elípticas de Legendre, o que simplifica a expressão de cada isogenia. Além disso, selecionando cuidadosamente o tipo de isogenias a serem computadas, conseguimos reunir cálculos de raiz quadrada em duas etapas consecutivas do algoritmo de Sutherland em apenas um único cálculo de quarta raiz (com experimentalmente quase o mesmo custo de um cálculo de raiz quadrada única). Os resultados dos nossos experimentos usando Magma apoiam nosso argumento; para casos de característica p de comprimentos de 768 bits a 1024 bits, nosso algoritmo proposto para características p≡1 (mod 4) é executado em cerca de 61.5% do tempo e para características p≡3 (mod 4) também é executado em cerca de 54.9% do tempo em comparação com o algoritmo de Sutherland.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.9 pp.1119-1130
Data de publicação
2023/09/01
Publicitada
2023/03/07
ISSN online
1745-1337
DOI
10.1587/transfun.2022DMP0002
Tipo de Manuscrito
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Categoria
Criptografia e Segurança da Informação

autores

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

Palavra-chave