next up previous
Next: Acknowledgements: Up: Quantum computation: a tutorial Previous: Prospects:


Here we describe Euclid's algorithm for finding the greatest common divisor () between a pair of numbers [38]. The algorithm proceeds by calculating the sequence of divisions with remainder for these numbers:

where the are the quotients and at each stage. The last non-zero remainder yields the answer, i.e., . For example, the sequence

shows that in just two steps. The worst case number of steps required to complete Euclid's algorithm is .

Samuel L.~Braunstein
Wed Aug 23 11:54:31 IDT 1995