Analysis of generalized continued fraction algorithms over polynomials
Analysis of generalized continued fraction algorithms over polynomials
复制标题
DOI：
10.1016/j.ffa.2021.101849
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
V. Berthé;H. Nakada;Rie Natsui;B. Vallée
中科院分区：
文献类型：
--
作者：
V. Berthé;H. Nakada;Rie Natsui;B. Vallée
我们研究和比较自然推广的欧几里得算法的多项式系数在有限域。这导致了gcd算法及其相关的连分式映射。gcd算法作用于多项式的三元组，并分别依赖于二维版本的Brun，Jacobi-Perron和全减连分式映射。首先，我们提供了一个统一的框架，这些算法和相关的连分式映射。然后，我们分析各种成本的gcd算法，包括迭代次数和两个版本的位复杂度，对应于两个表示的多项式（通常和稀疏的）。我们还研究了相关的二维连分式映射，证明了Haar测度的不变性和遍历性。我们推导出相应的成本估计截断轨迹的行动下，这些连分式地图，获得感谢他们的转移算子，我们比较了两种模式（gcd算法及其相关的连分式地图）。证明生成函数作为传递算子的主导本征值出现确实允许模型之间的精细比较。
We study and compare natural generalizations of Euclid's algorithm for polynomials with coefficients in a finite field. This leads to gcd algorithms together with their associated continued fraction maps. The gcd algorithms act on triples of polynomials and rely on two-dimensional versions of the Brun, Jacobi–Perron and fully subtractive continued fraction maps, respectively. We first provide a unified framework for these algorithms and their associated continued fraction maps. We then analyse various costs for the gcd algorithms, including the number of iterations and two versions of the bit-complexity, corresponding to two representations of polynomials (the usual and the sparse one). We also study the associated two-dimensional continued fraction maps and prove the invariance and the ergodicity of the Haar measure. We deduce corresponding estimates for the costs of truncated trajectories under the action of these continued fraction maps, obtained thanks to their transfer operators, and we compare the two models (gcd algorithms and their associated continued fraction maps). Proving that the generating functions appear as dominant eigenvalues of the transfer operator allows indeed a fine comparison between the models.