Some Mathematical Preliminaries

To explain the public-key cryptosystems, we must introduce basic mathematics. Taking the time to absorb these fairly elementary ideas will greatly enrich the understanding of how public-key cryptosystems work. If these ideas cause some difficulty, then there are a couple of alternative approaches that could be taken listed below:

1. Take a short break from reading this chapter in order to study the Mathematics Appendix. It will not take long, and the background material explains all that’s needed to understand these very elegant public-key cryptosystems. We recommend this approach since we genuinely believe it’s not hard, even for those with a fear of mathematics, to fully understand these very elegant public-key cryptosystems.

2. Skip through mathematics and try to grasp the essence of what’s going on. That’s a perfectly valid option, although the details of these public-key cryptosystems will probably remain somewhat ‘fuzzy.’

The main mathematical ideas we’ll need are discussed below.

Primes

A prime number, which we’ll refer to as a prime, is a number for which there are no numbers other than itself and 1 that divide it ‘neatly’—that is, without a remainder. The numbers that neatly divide another number are factors.

A prime has no factors except itself and 1. For example, 17 is a prime since the only numbers that divide it neatly are 1 and 17. On the other hand, 14 is not a prime since 2 and 7 divide it neatly and are, therefore, factors of 14. There is an infinite number of primes, with the smallest ten primes being 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. Primes play a very important role in mathematics and a particularly important role in cryptography.

Here we have an actual coded example of checking if a number is a prime: