8: Number Theory
- Page ID
- 48257
Number theory is the study of the integers. Why anyone would want to study the integers may not be obvious. First of all, what’s to know? There’s 0, there’s 1, 2, 3, and so on, and, oh yeah, -1, -2, . . . . Which one don’t you understand? What practical value is there in it?
The mathematician G. H. Hardy delighted at its impracticality. He wrote:
[Number theorists] may be justified in rejoicing that there is one science, at any rate, and that their own, whose very remoteness from ordinary human activities should keep it gentle and clean.
Hardy was especially concerned that number theory not be used in warfare; he was a pacifist. You may applaud his sentiments, but he got it wrong: number theory underlies modern cryptography, which is what makes secure online communication possible. Secure communication is of course crucial in war—leaving poor Hardy spinning in his grave. It’s also central to online commerce. Every time you buy a book from Amazon, use a certificate to access a web page, or use a PayPal account, you are relying on number theoretic algorithms.
Number theory also provides an excellent environment for us to practice and apply the proof techniques that we developed in previous chapters. We’ll work out properties of greatest common divisors (gcd’s) and use them to prove that integers factor uniquely into primes. Then we’ll introduce modular arithmetic and work out enough of its properties to explain the RSA public key crypto-system.
Since we’ll be focusing on properties of the integers, we’ll adopt the default convention in this chapter that variables range over the set, \(\mathbb{Z}\), of integers.
- 8.11: RSA Public Key Encryption
- In 1977, Ronald Rivest, Adi Shamir, and Leonard Adleman at MIT proposed a highly secure cryptosystem, called RSA, based on number theory. The purpose of the RSA scheme is to transmit secret messages over public communication channels. As with Turing’s codes, the messages transmitted are nonnegative integers of some fixed size.