Distributional analysis of GCD algorithms via the ergodic theory of random dynamical systems

整数对的最大公约数（GCD）的计算是计算机代数中的一项基本任务，并且在诸如公钥加密的实现和妥协等具有深刻现实意义的问题中作为子任务出现。在过去的二十年中，对GCD计算算法运行时间的数学严谨研究取得了重大的里程碑，但重要的问题仍然存在，其中与二进制欧几里得算法有关的问题可能是最突出的。在这个项目中，我们将严格研究几种重要的GCD计算算法中步骤数的分布。这些结果将允许计算机程序员以相当精确和确定的方式估计这些算法在处理大整数时的预期运行时间。二进制欧几里得算法是欧几里得计算GCD的经典算法的现代改进，它是利用现代计算机使用二进制运算的事实而设计的。二进制欧几里得算法可以被认为是计算最大公约数的基本算法之一，并且是Donald Knuth的影响深远的教科书系列“计算机编程艺术”中仅有的三种GCD算法之一。我们将试图证明Donald Knuth提出的几个猜想，这些猜想与R. P. Brent提出的二进制欧几里得算法的运算数学模型有关。这些猜想的有效性将意味着对于随机选择的大输入，该算法的平均运行时间的新的严格渐近估计。我们还将严格调查运行时间偏离该平均值的方式，目的是证明运行时间围绕其平均值正态分布。Douglas Hensley（1994）证明了欧几里德描述的经典GCD算法所进行的除法步数是关于其均值的渐近正态分布。虽然平均数的渐近值的封闭形式描述已经知道了几十年，但据信不存在相应的方差的封闭形式表达式，并且迄今为止还没有发表过对该常数计算的研究。我们的目标是对这个方差的估计给出一个数学上严格的处理。最后，我们旨在证明D. stehl<s:1>和P. Zimmermann最近提出的用于整型GCD计算的二进算法的运行时间是关于其平均运行时间的渐近正态分布。

The computation of the greatest common divisor (GCD) of a pair of integers is a fundamental task in computer algebra and arises as a subtask in problems of profound real-world significance such as both the implementation and the compromise of public key cryptography. The mathematically rigorous investigation of the running time of algorithms for GCD computation has achieved significant milestones in the last two decades but important problems remain open, of which those relating to the binary Euclidean algorithm are perhaps the most prominent. In this project we will rigorously investigate the distribution of the number of steps in several important algorithms for GCD computation. These results would allow computer programmers to estimate the anticipated running time of these algorithms when applied to large integers with considerable precision and certainty.The binary Euclidean algorithm is a modern modification of the classical algorithm for GCD computation described by Euclid which is designed to exploit the fact that modern computers operate using binary arithmetic. The binary Euclidean algorithm may be considered to be one of the fundamental algorithms for the computation of greatest common divisors, and is one of only three GCD algorithms described in every edition of Donald Knuth's seminal textbook series "The Art of Computer Programming". We will attempt to prove several conjectures posed by Donald Knuth which relate to a mathematical model for the operation of the binary Euclidean algorithm proposed by R. P. Brent. The validity of these conjectures would imply new rigorous asymptotic estimates for the average running time of this algorithm for randomly-selected large inputs. We will also rigorously investigate the manner in which the running time deviates from this average, with the objective of proving that the running times are distributed normally about their mean value. It was shown by Douglas Hensley in 1994 that the number of division steps undertaken by the classical GCD algorithm described by Euclid is asymptotically normally distributed about its mean value. While a closed-form description of the asymptotic value of the mean has been known for several decades, it is believed that no corresponding closed-form expression for the variance exists, and to date no investigation of the computation of this constant has been published. We aim to give a mathematically rigorous treatment of the estimation of this variance. Finally we aim to prove that the running times of the 2-adic algorithm for integer GCD computation introduced recently by D. Stehlé and P. Zimmermann are asymptotically normally distributed about their mean running time.