Analysis of generalized continued fraction algorithms over polynomials (Q2031651)

Its well knew that the greatest common divisor (gcd) computation for univariate polynomials is a basic operation in computer algebra and Euclid's algorithm completely solves the problem of gcd computation for two entries. However, there does not exist a canonical generalization of Euclid's algorithm when working with at least three entries. Three generalized Euclidean algorithms for polynomials with coefficients in a finite field, inspired by classical multidimensional continued fraction maps, namely the Jacobi-Perron, the Brun, and the fully subtractive maps were chosen and compared in this paper. The two-dimensional versions of the Jacobi-Perron, the Brun, and the fully subtractive algorithms are associated with continued fraction maps. A unified framework for these algorithms and their associated continued fraction maps are provided. The convergence of the continued fraction maps was discussed. The bivariate generating functions are the main tool of the study. This enables in particular to exhibit asymptotic Gaussian laws. The various costs for the gcd algorithms, including the number of iterations and two versions of the bit-complexity, corresponding to two representations of polynomials analyzed in the paper. The associated two-dimensional continued fraction maps are studied and the invariance and the ergodicity of the Haar measure are proved. The authors obtain corresponding estimates for the costs of truncated trajectories under the action of these continued fraction maps and are compared the two models (gcd algorithms and their associated continued fraction maps).