Chapter 8. Introduction to Number Theory

[Page 234]

8.1 Prime Numbers

8.2 Fermat's and Euler's Theorems

Fermat's Theorem

Euler's Totient Function

Euler's Theorem

8.3 Testing for Primality

Miller-Rabin Algorithm

A Deterministic Primality Algorithm

Distribution of Primes

8.4 The Chinese Remainder Theorem

8.5 Discrete Logarithms

The Powers of an Integer, Modulo n

Logarithms for Modular Arithmetic

Calculation of Discrete Logarithms

8.6 Recommended Reading and Web Site

8.7 Key Terms, Review Questions, and Problems

Key Terms

Review Questions

Problems

---

[Page 235]

The Devil said to Daniel Webster: "Set me a task I can't carry out, and I'll give you anything in the world you ask for."

Daniel Webster: "Fair enough. Prove that for n greater than 2, the equation aⁿ + bⁿ = cⁿ has no non-trivial solution in the integers."

They agreed on a three-day period for the labor, and the Devil disappeared.

At the end of three days, the Devil presented himself, haggard, jumpy, biting his lip. Daniel Webster said to him, "Well, how did you do at my task? Did you prove the theorem?"

"Eh? No ... no, I haven't proved it."

"Then I can have whatever I ask for? Money? The Presidency?"

"What? Oh, thatof course. But listen! If we could just prove the following two lemmas"

The Mathematical Magpie, Clifton Fadiman

Key Points

• A prime number is an integer that can only be divided without remainder by positive and negative values of itself and 1. Prime numbers play a critical role both in number theory and in cryptography.

• Two theorems that play important roles in public-key cryptography are Fermat's theorem and Euler's theorem.

• An important requirement in a number of cryptographic algorithms is the ability to choose a large prime number. An area of ongoing research is the development of efficient algorithms for determining if a randomly chosen large integer is a prime number.

• Discrete logarithms are fundamental to a number of public-key algorithms. Discrete logarithms are analogous to ordinary logarithms, but operate over modular arithmetic.

A number of concepts from number theory are essential in the design of public-key cryptographic algorithms. This chapter provides an overview of the concepts referred to in other chapters. The reader familiar with these topics can safely skip this chapter.

As with Chapter 4, this chapter includes a number of examples, each of which is highlighted in a shaded box.