Introduction to Cryptography with Open-Source Software

Chapter 2

Basic number th eory

This chapter provides the mathematical background for much o f the rest of

the boo k. In particular, it inves tigates:

• Prime numbers, their definition and uses.

• Factorization.

• Modular arithmetic, including powers and inverses.

• Fermat’s theorem, Euler’s totient function and Euler’s generalization of

Fermat’s theorem.

• The Chinese remainder theorem.

• The Euclidea n algorithm, both standard and extended forms.

• Quadra tic residues and the L e gendre sy mbol.

• Some methods of primality testing.

2.1 Introduction

Much modern cryptography is based around the theory of numbers, in par-

ticular prime numbers and their prop ...