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

点击翻译按钮获取中文摘要

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.