Euclid shows Alice how to find her deciphering number
Alice's computer can find d using an algebraic tool that is over2,300 years old, the Euclidean Algorithm, which will be explained in a moment. Eve's computer could of course do the same thing if itjust knew which equation to solve. However, since p and q are private to Alice, so is(p-1)(q-1)and Eve does not knowwhere to begin.
Returning to the Euclidean Algorithm, this begins from the observation that it is possible to find the highest commonfactor(hcf)of two numbers a〉b by successive subtraction.(The hcfis also known as the gcd–greatest common divisor.)Wejust note that r=a-b has the propertythat any common factor of anytwo of the three numbers a, b, and r will also be a factor of the third.For example, ifc is a common factor of a and b, so that a=ca1 and b=cb1 say,we seethatr=a-b=ca1-cb1=c(a1-b1), givingus a factorization of r involving the divisor c. In particular, the hcf of a and b is the same as the hcfof b and r. Since both these numbers are less than a, we now have the same problem but applied to a smaller number pair. Repetition of this idea then will eventually lead to a pair where the hcfis obvious.(Indeed, the two numbers in hand will eventually be the same, for ifnot we could proceed one more step;their common value is then the number we seek.)
