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.

This project aims to enhance our understanding of a class of fundamental number-theoretic algorithms which find application in both the implementation and the compromise of number-theoretic public key cryptography. In the long term, a better understanding of these algorithms holds out the possibility of leading to the design of more efficient algorithms in the future, thereby having the potential to improve the efficiency of future cryptographic computer software. However, the abstract and theoretical nature of the work means that the results are not best suited for direct dissemination to industry, and so this impact will take place via the intermediate stage of disseminating these results to the theoretical computer science community. Since one of the goals of this research is to resolve a long-standing open question on the running time of a fundamental algorithm - the binary GCD algorithm - it is hoped that the communication of this result to the computer science community will lead ultimately to its being more widely disseminated via textbooks.

As can be the case in pure mathematics, the methods which we develop in this research project may ultimately find application in areas which are not a priori related to the immediate topic of study. As such we believe that it is also beneficial for these results to be disseminated to the general community of mathematicians in furtherance of this type of impact.