Mastering Algorithms with Perl

Chapter 12.  Number Theory

Why is it that we entertain the belief that for every purpose odd numbers are the most effectual?

—Pliny the Elder (23-79), Natural History

Number theory is thousands of years old. For most of those millennia, it’s been “pure” mathematics, meaning that it had little practical application. That has changed in the last few decades; many of the most important advances in cryptography resulted from number theory. In this chapter, we concentrate on prime numbers and modular exponentiation, both of which are invaluable for the next chapter: cryptography.

Before we can talk about prime numbers, we’ll first explore the basics of number theory: the greatest common divisor (GCD) and least common multiple (LCM), and techniques for performing modular arithmetic. Then we’ll use these techniques to find large prime numbers. (We’ll also demonstrate caching techniques to make the search faster.) Finally, we’ll spend a few pages on diversions: three simple Perl programs that illustrate some unsolved problems in mathematics.

This is the most theoretical chapter in the book, but don’t let that scare you. The mathematics involved is quite simple.

Basic Number Theory

Most of this section is about divisors and remainders. A divisor is a number which evenly divides another number, its multiple. (2 is a divisor of 6, 6 is a multiple of 2.) A remainder is the amount left over when you divide one number into another. (When you divide 7 by 2, the remainder is 1.)

We will generally ...