The extended Euclidean algorithm on polynomials, and the computational efficiency of hyperelliptic cryptosystems
type: Item
instance of: scholarly article
title: The extended Euclidean algorithm on polynomials, and the computational efficiency of hyperelliptic cryptosystems
zbMATH Open document ID: 0985.94031
DOI: 10.1023/A:1011215802656
author: Andreas Enge
published in: Designs, Codes and Cryptography
publication date: 2001-11-04T00:00:00Z
review text: The author considers the computational efficiency of public key cryptosystems using Jacobians of hyperelliptic curves over a finite field. Several algorithms for adding or reducing divisors, due to such authors as \textit{D. G. Cantor} [Math. Comput. 48, 95-101 (1987; Zbl 0613.14022)] and \textit{S. Paulus} and \textit{A. Stein} [Lect. Notes Comput. Sci. 1423, 576-591 (1998; Zbl 0935.11052)], are generalized to include the case of characteristic two, and the author determines the average number of multiplications and inversions involved in these algorithms. A key tool used in the algorithms is the extended Euclidean algorithm, which has also been analyzed by \textit{K. Ma} and \textit{J. von zur Gathen} [J. Symb. Comput. 9, 429-455 (1990; Zbl 0698.68045)]. The author concludes that, given a desired security level, hyperelliptic cryptosystems should preferably be implemented in characteristic two. Also, because of specialized algorithms in the elliptic curve case, hyperelliptic cryptosystems based on the generic algorithms studied here are less efficient than elliptic curve cryptosystems.
reviewed by: Robert F. Lax
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 14G50
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 11Y16
zbMATH DE Number: 1626364
zbMATH Keywords: Euclidean algorithm
zbMATH Keywords: average complexity
zbMATH Keywords: hyperelliptic cryptosystem
MaRDI profile type: MaRDI publication profile
full work available at URL: a:1011215802656
OpenAlex ID: W1491854237
Recommended article: Q3840091
Recommended article: Hyperelliptic cryptosystems
Recommended article: Formulae for arithmetic on genus 2 hyperelliptic curves
Recommended article: Q4530230
Recommended article: Q4664851
description: scientific article; zbMATH DE number 1626364