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

通过随机动力系统遍历理论进行 GCD 算法的分布分析

• 批准号: EP/L026953/1
• 负责人: Ian Morris
• 金额: $ 11.7万
• 依托单位: University of Surrey
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2014
• 资助国家: 英国
• 起止时间: 2014 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FL026953%2F1
• 关键词: Distributional; analysis; GCD; algorithms; via

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.

一对整数的最大公约数 (GCD) 的计算是计算机代数中的一项基本任务，并且是作为具有深远现实意义的问题（例如公钥密码学的实现和妥协）的子任务而出现的。在过去的二十年里，对 GCD 计算算法的运行时间进行严格的数学研究已经取得了重大的里程碑，但重要的问题仍然悬而未决，其中与二进制欧几里得算法相关的问题可能是最突出的。在这个项目中，我们将严格研究 GCD 计算的几个重要算法中步数的分布。这些结果将允许计算机程序员以相当的精度和确定性估计这些算法在应用于大整数时的预期运行时间。二进制欧几里得算法是欧几里得描述的 GCD 计算经典算法的现代修改，旨在利用现代计算机使用二进制算术运行的事实。二元欧几里得算法可以被认为是计算最大公约数的基本算法之一，并且是 Donald Knuth 的开创性教科书系列“计算机编程的艺术”的每个版本中描述的仅有的三种 GCD 算法之一。我们将尝试证明 Donald Knuth 提出的几个猜想，这些猜想与 R. P. Brent 提出的二进制欧几里得算法的操作数学模型有关。这些猜想的有效性意味着对随机选择的大输入的该算法的平均运行时间进行新的严格渐近估计。我们还将严格研究运行时间偏离该平均值的方式，目的是证明运行时间关于其平均值呈正态分布。 Douglas Hensley 在 1994 年证明，欧几里得描述的经典 GCD 算法所采用的除法步数关于其平均值呈渐近正态分布。虽然平均值渐近值的封闭式描述已为人所知数十年，但据信不存在相应的方差封闭式表达式，并且迄今为止尚未发表对该常数的计算的研究。我们的目标是对这种方差的估计进行严格的数学处理。最后，我们的目标是证明 D. Stehlé 和 P. Zimmermann 最近提出的用于整数 GCD 计算的 2-adic 算法的运行时间关于其平均运行时间呈渐近正态分布。

项目成果

Generic properties of the lower spectral radius for some low-rank pairs of matrices

一些低秩矩阵对的下谱半径的一般性质

• DOI: 10.1016/j.laa.2017.02.023
• 发表时间: 2017
• 期刊: Linear Algebra and its Applications
• 影响因子: 1.1
• 作者: Morris I

On equality of Hausdorff and affinity dimensions, via self-affine measures on positive subsystems

• DOI: 10.1090/tran/7334
• 发表时间: 2016-02
• 期刊: Transactions of the American Mathematical Society
• 影响因子: 1.3
• 作者: I. Morris;Pablo Shmerkin

A rigorous version of R.P. Brent's model for the binary Euclidean algorithm

R.P. Brent 二进制欧几里得算法模型的严格版本

• DOI: 10.1016/j.aim.2015.12.008
• 发表时间: 2016
• 期刊: Advances in Mathematics
• 影响因子: 1.7
• 作者: Morris I

Characterization of dominated splittings for operator cocycles acting on Banach spaces

作用于 Banach 空间的算子余循环的支配分裂的表征

• DOI: 10.48550/arxiv.1512.07602
• 发表时间: 2015
• 期刊: arXiv e-prints
• 作者: Blumenthal Alex

Structure of equilibrium states on self-affine sets and strict monotonicity of affinity dimension

自仿射集上平衡态的结构和亲和维数的严格单调性

• DOI: 10.48550/arxiv.1609.07360
• 发表时间: 2016
• 作者: Käenmäki A