The Euclidean algorithm, the algorithm to compute the greatest common divisor, or , of two numbers, dates back to antiquity (obviously). We can use it to make a fast test for primality, at least up to some confidence—and that’s where the inclusion-exclusion principle comes in.

Let us begin by the Euclidean algorithm. Originally, the algorithm was done by successive subtraction (and becomes quickly tedious as numbers grow), but the modern version, at least the one that I know of, uses divisions and remainders (modulo), and computes the of two numbers and in (counting division as an operation), which is *very* fast.

Read the rest of this entry »