Analysis of generalized continued fraction algorithms over polynomials
type: Item
instance of: scholarly article
title: Analysis of generalized continued fraction algorithms over polynomials
zbMATH Open document ID: 1472.11207
author: Hitoshi Nakada
author: Rie Natsui
author: Valérie Berthé
author: Brigitte Vallée
published in: Finite Fields and their Applications
publication date: 2021-06-10T00:00:00Z
review text: 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).
reviewed by: Mykhaylo Pahirya
Mathematics Subject Classification ID: 11J70
Mathematics Subject Classification ID: 11K50
Mathematics Subject Classification ID: 11K55
Mathematics Subject Classification ID: 68W40
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 37A44
zbMATH DE Number: 7357324
zbMATH Keywords: gcd algorithms for polynomials over finite fields
zbMATH Keywords: multidimensional continued fractions
zbMATH Keywords: Laurent formal power series
zbMATH Keywords: costs and bit-complexities
zbMATH Keywords: Gaussian laws
zbMATH Keywords: analytic combinatorics
zbMATH Keywords: generating functions
zbMATH Keywords: dynamical systems
zbMATH Keywords: Haar measure
zbMATH Keywords: transfer operators
MaRDI profile type: Publication
full work available at URL: j.ffa.2021.101849
OpenAlex ID: W3157802280
cites work: Q4509266
cites work: Euclidean algorithms are Gaussian
cites work: Convergence of the Brun algorithm over the field of formal power series
cites work: On continued fraction expansions in positive characteristic: equivalence relations and some metric properties
cites work: Probabilistic analyses of the plain multiple gcd algorithm
cites work: The Brun gcd algorithm in high dimensions is almost always subtractive
cites work: Fine costs for Euclid's algorithm on polynomials and Farey maps
cites work: Q5557748
cites work: The convergence of the generalised Selmer algorithm
cites work: Q4292040
cites work: Q3549563
cites work: On Schweiger's problems on fully subtractive algorithms
cites work: The statistics of continued fractions for polynomials over a finite field
cites work: Q4406533
cites work: On convergence rates in the central limit theorems for combinatorial structures
cites work: Q4462461
cites work: The modified Jacobi-Perron algorithm over \(\mathbb F_q (X)^d\)
cites work: The exact length of the Euclidean algorithm in [ X ]
cites work: Gaussian laws for the main parameters of the Euclid algorithms
cites work: Metric properties and exceptional sets of \(\beta \)-expansions over formal Laurent series
cites work: On the thermodynamic formalism for the Gauss map
cites work: The three-dimensional Poincaré continued fraction algorithm
cites work: Q5614752
cites work: Q5668884
cites work: Q4185090
cites work: Non-negative matrices and Markov chains. 2nd ed
cites work: Q4501766
cites work: Q4179411
cites work: Euclidean dynamics
cites work: Interval exchange transformations
cites work: On the sum of degrees of digits occurring in continued fraction expansions of Laurent series
DOI: 10.1016/J.FFA.2021.101849
description: scientific article; zbMATH DE number 7357324