Abstract

The Euclidean algorithm on the natural numbers ℕ = {0,1,…} can be specified succinctly by the recursive programwhere rem is the remainder in the division of a by b, the unique natural number r such that for some natural number q,It is an algorithm from the remainder function rem, meaning that in computing its time complexity function cε, we assume that the values rem are provided on demand by some “oracle” in one “time unit”. It is easy to prove thatMuch more is known about cε, but this simple-to-prove upper bound suggests the proper formulation of the Euclidean's optimality among its peers—algorithms from rem:Conjecture. If an algorithm α computes gcd from rem with time complexity cα, then there is a rational number r > 0 such that for infinitely many pairs a > b > 1, cα > r log2a.