×

A unifying framework for the analysis of a class of Euclidean algorithms. (English) Zbl 0979.11058

Gonnet, Gastón H. (ed.) et al., LATIN 2000: Theoretical informatics. 4th Latin American symposium, Punta del Este, Uruguay, April 10-14, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1776, 343-354 (2000).
The author determines the average-case complexity of variants of a) the Euclidean algorithm for computing the greatest common divisor of two integers and b) algorithms for calculating Jacobi symbols. Interpreting these algorithms as continued fraction expansions, she obtains transformation matrices for each step. These transfer operators lead to special Dirichlet series as generating functions. Their analytical properties can be deduced from the spectrum of suitable Ruelle operators. The results are then obtained from the coefficients of those Dirichlet series by a Tauberian theorem.
For the entire collection see [Zbl 0935.00049].
Reviewer: M.Pohst (Berlin)

MSC:

11Y16 Number-theoretic algorithms; complexity
PDFBibTeX XMLCite