Introduction

Number theory was once viewed as a beautiful but largely useless subject in pure mathematics.

Today number-theoretic algorithms are used widely, due in part to the invention of cryptographic schemes based on large prime numbers.

The feasibility of these schemes rests on our ability to find large primes easily, while their security rests on our inability to factor the product of large primes. This chapter presents some of the number theory and associated algorithms that underlie such applications.