The extended Euclidean algorithm on polynomials, and the computational efficiency of hyperelliptic cryptosystems (Q5939677)

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.