The Joy of Cryptography

0 – Review of Concepts & Notation

The material in this section is meant as a review. Despite that, many students report that they nd this review useful for the rest of the book.

0.1 Logs & Exponents

You probably learned (and then forgot) these identities in middle school or high school:

Well, it’s time to get reacquainted with them again.

In particular, never ever write (xa)(xb ) = xab . If you write this, your cryptography instructor will realize that life is too short, immediately resign from teaching, and join a traveling circus. But not before changing your grade in the course to a zero.

0.2 Modular Arithmetic

We write the set of integers as:

and the set of natural numbers (nonnegative integers) as:

Note that 0 is considered a natural number.

Definition 0.1
For x ,n ∈ Z, we say that n divides x (or x is a multiple of n), and write n | x , if there exists an integer k such that x = kn.

Remember that the definitions apply to both positive and negative numbers (and to zero). We generally only care about this definition in the case where n is positive, but it is common to consider both positive and negative values of x .

Example
7 divides 84 because we can write 84 = 12 · 7.
7 divides 0 because we can write 0 = 0 · 7.
7 divides −77 because we can write −77 = (−11) · 7.
−7 divides 42 because we can write 42 = (−6) · (−7).
1 divides every integer (so does −1). The only integer that 0 divides is itself.

Definition 0.2 (% operator)

Let n be a positive integer, and let a be any integer. The expression a % n (usually read as “a mod n”) represents the remainder after dividing a by n. More formally, a % n is the unique r ∈ {0, . . . ,n − 1} such that n | (a − r ).1

Pay special attention to the fact that a %n is always a nonnegative number, even if a is negative. A good way to remember how this works is:

a is (a % n) more than a multiple of n.

Example
21 % 7 = 0 because 21 = 3 · 7 + 0.
20 % 7 = 6 because 20 = 2 · 7 + 6.
−20 % 7 = 1 because −20 = (−3) · 7 + 1. (−20 is one more than a multiple of 7.)
−1 % 7 = 6 because −1 = (−1) · 7 + 6.

Unfortunately, some programming languages define % for negative numbers as (−a)% n = −(a % n), so they would define −20 % 7 to be −(20 % 7) = −6. This is madness, and it’s about time we stood up to these programming language designers and smashed them over the head with some mathematical truth! For now, if you are using some programming environment to play around with the concepts in the class, be sure to check whether it defines % in the correct way.

Definition 0.3 (Zn)
For positive n, we write Zn def = {0, . . . ,n − 1} to denote the set of integers modulo n. These are the possible remainders one obtains by dividing by n.2

Definition 0.4(≡n)
For positive n, we say that integers a and b are congruent modulo n, and write a ≡n b, if n | (a − b). An alternative definition is that a ≡n b if and only if a % n = b % n.

You’ll be in a better position to succeed in this class if you can understand the (subtle) distinction between a ≡n b and a = b % n:

a ≡n b:
In this expression, a and b can be integers of any size, and any sign. The left and right side have a certain relationship modulo n.

a = b % n:
This expression says that two integers are equal. The “=” rather than “≡” is your clue that the expression refers to equality over the integers. “b % n” on the right-hand side is an operation performed on two integers that returns an integer result. The result of b % n is an integer in the range {0, . . . ,n − 1}.

Example
“99 ≡10 19” is true. Applying the definition, you can see that 10 divides 99 − 19.
On the other hand, “99 = 19 % 10” is false. The right-hand side evaluates to the integer 9, but 99 and 9 are different integers.

In short, expressions like a ≡n b make sense for any a,b (including negative!), but expressions like a = b % n make sense only if a ∈ Zn .