EPSRC Reference: 
EP/L026953/1 
Title: 
Distributional analysis of GCD algorithms via the ergodic theory of random dynamical systems 
Principal Investigator: 
Morris, Dr I D 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Mathematics 
Organisation: 
University of Surrey 
Scheme: 
First Grant  Revised 2009 
Starts: 
01 July 2014 
Ends: 
30 June 2016 
Value (£): 
91,795

EPSRC Research Topic Classifications: 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 

Summary on Grant Application Form 
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 realworld 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 randomlyselected 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 closedform description of the asymptotic value of the mean has been known for several decades, it is believed that no corresponding closedform 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 2adic algorithm for integer GCD computation introduced recently by D. Stehlé and P. Zimmermann are asymptotically normally distributed about their mean running time.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

Date Materialised 


Sectors submitted by the Researcher 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Project URL: 

Further Information: 

Organisation Website: 
http://www.surrey.ac.uk 