Elliptic curve point counting over finite fields with Gaussian normal basis
type: Item
instance of: scholarly article
title: Elliptic curve point counting over finite fields with Gaussian normal basis
zbMATH Open document ID: 1114.11057
author: Je Hong Park
author: Jung Youl Park
author: Sang Geun Hahn
published in: Proceedings of the Japan Academy. Series A
publication date: 2003-01-01T00:00:00Z
full work available at URL: https://projecteuclid.org/euclid.pja/1116442544
review text: This short note describes an improvement on \textit{P. Gaudry's} article [Advances in cryptology - ASIACRYPT 2002, 311--327 (2002; Zbl 1065.11098)] for point counting on elliptic curves over binary fields. The method stems from \textit{T. Satoh} [J. Ramanujan Math. Soc. 15, 247--270 (2000; Zbl 1009.11051)] and the improvement in \textit{T. Satoh}, \textit{B. Skjernaa}, and \textit{Y. Taguchi} [Finite Fields Appl. 9, 89--101 (2003; Zbl 1106.14302)] combined with the AGM method due to Mestre. The authors propose to use a Gaussian normal basis representation to allow an efficient computation of the norm and show that the basis can also be used for the \(p\)-adic fields one lifts to. This approach leads to faster implementations if there exists a basis of type \(1\) or \(2\) as this allows to multiply efficiently.
reviewed by: Tanja Lange
Mathematics Subject Classification ID: 11G20
Mathematics Subject Classification ID: 11G07
Mathematics Subject Classification ID: 11T71
zbMATH DE Number: 2024710
zbMATH Keywords: point counting
zbMATH Keywords: elliptic curve
zbMATH Keywords: elliptic curves over binary fields
zbMATH Keywords: Gaussian normal basis
MaRDI profile type: Publication
OpenAlex ID: W2062264340
cites work: An extension of Satoh's algorithm and its implementation
cites work: A Comparison and a Combination of SST and AGM Algorithms for Counting Points of Elliptic Curves in Characteristic 2
cites work: Q4737493
cites work: The canonical lift of an ordinary elliptic curve over a finite field and its point counting
cites work: Q4737474
cites work: Fast computation of canonical lifts of elliptic curves and its application to point counting.
cites work: Satoh's algorithm in characteristic 2
cites work: Q3149669
DOI: 10.3792/PJAA.79.5
description: scientific article; zbMATH DE number 2024710