An Introduction to Number Theory with Cryptography

James Kraft, Lawrence Washington

• Publisher: Chapman and Hall/CRC
• Year: 2018
• Print ISBN: 9781032476353
• eBook ISBN: 9781351664103
• Edition: 2
• Topic: Computer Science
• Subtopic: Cryptography
• Index: Computer Science

Building on the success of the first edition, An Introduction to Number Theory with Cryptography, Second Edition, increases coverage of the popular and important topic of cryptography, integrating it with traditional topics in number theory.

The authors have written the text in an engaging style to reflect number theory's increasing popularity. The book is designed to be used by sophomore, junior, and senior undergraduates, but it is also accessible to advanced high school students and is appropriate for independent study. It includes a few more advanced topics for students who wish to explore beyond the traditional curriculum.

Features of the second edition include

• Over 800 exercises, projects, and computer explorations

• Increased coverage of cryptography, including Vigenere, Stream, Transposition,and Block ciphers, along with RSA and discrete log-based systems

• "Check Your Understanding" questions for instant feedback to students

• New Appendices on "What is a proof?" and on Matrices

• Select basic (pre-RSA) cryptography now placed in an earlier chapter so that the topic can be covered right after the basic material on congruences

• Answers and hints for odd-numbered problems

About the Authors:

Jim Kraft received his Ph.D. from the University of Maryland in 1987 and has published several research papers in algebraic number theory. His previous teaching positions include the University of Rochester, St. Mary's College of California, and Ithaca College, and he has also worked in communications security. Dr. Kraft currently teaches mathematics at the Gilman School.

Larry Washington received his Ph.D. from Princeton University in 1974 and has published extensively in number theory, including books on cryptography (with Wade Trappe), cyclotomic fields, and elliptic curves. Dr. Washington is currently Professor of Mathematics and Distinguished Scholar-Teacher at the University of Maryland.

Chapter 1

Introduction

At Columbia University there is a Babylonian clay tablet called Plimpton 322 that is over 3800 years old and not much larger than a cell phone. Written in cuneiform script with four columns and 15 rows, it contains numbers written in base 60 (just as base 10 is standard today, base 60 was standard in Babylon). Each row gives a Pythagorean triple, that is, three whole numbers x, y, z satisfying

$x^2+y^2=z^2$

(for example, 3² + 4² = 5² and 12709² + 13500² = 18541² are triples from the tablet). This is one of the earliest examples where integers are studied for their interesting properties, not just for counting objects. Throughout history, there has been a fascination with whole numbers. For example, the Pythagorean school (ca. 500 BCE) believed strongly that every quantity could be expressed in terms of integers or ratios of integers, and they successfully applied the idea to the theory of musical scales. However, this overriding belief received a sharp setback when one of Pythagoreans, possibly Hippasus, proved that $\sqrt{2}$ is irrational. There is a story, which may be apocryphal, that he discovered this at sea and was promptly thrown overboard by his fellow Pythagoreans. Despite their attempt at suppressing the truth, the news of this discovery soon got out. Nevertheless, even though irrational numbers exist and are plentiful, properties of integers are still important.

Approximately 200 years after Pythagoras, Euclid’s Elements, perhaps the most important mathematics book in history, was published. Although most people now think of the Elements as a book concerning geometry, a large portion of it is devoted to the theory of numbers. Euclid proves that there are infinitely many primes, demonstrates fundamental properties concerning divisibility of integers, and derives a formula that yields all possible Pythagorean triples, as well as many other seminal results. We will see and prove these results in the first five chapters of this book.

Number theory is a rich subject, with many aspects that are inextricably intertwined but which also retain their individual characters. In this introduction, we give a brief discussion of some of the ideas and some of the history of number theory as seen through the themes of Diophantine equations, modular arithmetic, the distribution of primes, and cryptography.

1.1 Diophantine Equations

Diophantus lived in Alexandria, Egypt, about 1800 years ago. His book Arithmetica gives methods for solving various algebraic equations and had a great influence on the development of algebra and number theory for many years. The part of number theory called Diophantine equations, which studies integer (and sometimes rational) solutions of equations, is named in his honor. However, the history of this subject goes back much before him. The Plimpton tablet shows that the Babylonians studied integer solutions of equations. Moreover, the Indian mathematician Baudhāyana (≈ 800 BCE) looked at the equation x² − 2y² = 1 and found the solutions (x, y) = (17, 12) and (577, 408). The latter gives the approximation 577/408 ≈ 1.4142157 for $\sqrt{2}$, which is the diagonal of the unit square. This was a remarkable achievement considering that, at the time, a standardized system of algebraic notation did not yet exist.

The equation

$x^2-n{y}^2=1,$

where n is a positive integer not a square, was studied by Brahmagupta (598-668) and later mathematicians. In 1768, Joseph-Louis Lagrange (1736-1813) presented the first published proof that this equation always has a nontrivial solution (that is, with y ≠ 0). Leonhard Euler (1707-1783) mistakenly attributed some work on this problem to the English mathematician John Pell (1611-1685), and ever since it has been known as Pell’s equation, but there is little evidence that Pell did any work on it. In Chapters 15 and 17, we show how to solve Pell’s equation, and in Chapter 19, we discuss its place in algebraic number theory.

Perhaps x² + y² = z², the equation for Pythagorean triples, is the most well-known Diophantine equation. Since sums of two nonzero squares can be a square, people began to wonder if this could be generalized. For example, Abu Mohammed Al-Khodjandi, who lived in the late 900s, claimed to have a proof that a sum of nonzero cubes cannot be a cube (that is, the equation x³ + y³ = z³ has no nonzero solutions). Unfortunately, our only knowledge of this comes from another manuscript, which mentions that Al-Khodjandi’s proof was defective, but gives no evidence to support this claim. The real excitement began when the great French mathematician Pierre de Fermat (1601-1665) penned a note in the margin of his copy of Diophantus’s Arithmetica saying that it is impossible to solve xⁿ + yⁿ = zⁿ in positive integers when n ≥ 3 and that he had found a truly marvelous proof that the margin was too small to contain. After Fermat’s son, Samuel Fermat, published an edition of Diophantus’s book that included his father’s comments, the claim became known as Fermat’s Last Theorem. Today, it is believed that he actually had proofs only in the cases n = 4 (the only surviving proof by Fermat of any of his results) and possibly n = 3. But the statement acquired a life of its own and led to many developments in mathematics. Euler is usually credited with the first complete proof that Fermat’s Last Theorem (abbreviated as FLT) is true for n = 3. Progress proceeded exponent by exponent, with Adrien-Marie Legendre (1752–1833) and Johann Peter Gustav Lejeune Dirichlet (1805-1859) each doing the case n = 5 around 1825 and Gabriel Lamé (1795-1870) treating n = 7 in 1839. Important general results were obtained by Sophie Germain (1776-1831), who showed that if p < 100 is prime and xyz is not a multiple of p, then x^p + y^p ≠ z^p.

The scene changed dramatically around 1850, when Ernst Eduard Kummer (1810-1893) developed his theory of ideal numbers, which are now known as ideals in ring theory. He used them to give general criteria that allowed him to prove FLT for all exponents up to 100, and many beyond that. His approach was a major step in the development of both algebraic number theory and abstract algebra, and it dominated the research on FLT until the 1980s. In the 1980s, new methods, based on work by Taniyama, Shimura, Weil, Serre, Langlands, Tunnell, Mazur, Frey, Ribet, and others, were brought to the problem, resulting in the proof of Fermat’s Last Theorem by Andrew Wiles (with the help of Richard Taylor) in 1994. The techniques developed during this period have opened up new areas of research and have also proved useful in solving many classical mathematical problems.

1.2 Modular Arithmetic

Suppose you divide 1234²⁵¹⁴⁷ by 25147. What is the remainder? Why should you care? A theorem of Fermat tells us that the remainder is 1234. Moreover, as we’ll see, results of this type are surprisingly vital in cryptographic applications (see Chapters 7, 9, and 12).

Questions about divisibility and remainders form the basis of modular arithmetic, which we introduce in Chapter 6. This is a very old topic and its development is implicit in the work of several early mathematicians. For example, the Chinese Remainder Theorem is a fundamental and essential result in modular arithmetic and was discussed by Sun Tzu around 1600 years ago.

Although early mathematicians discovered number theoretical results, the true beginnings of modern number theory began with the work of Fermat, whose contributions were both numerous and profound. We will discuss several of them in this book. For example, he proved that if a is a whole number and p is a prime, then a^p − a is always a multiple of p. Results such as this are best understood in terms of modular ar...

Table of contents

• Cover
• Title Page
• Copyright Page
• Dedication
• Table of Contents
• 1 Introduction
• 2 Divisibility
• 3 Linear Diophantine Equations
• 4 Unique Factorization
• 5 Applications of Unique Factorization
• 6 Congruences
• 7 Classical Cryptosystems
• 8 Fermat, Euler, and Wilson
• 9 RSA
• 10 Polynomial Congruences
• 11 Order and Primitive Roots
• 12 More Cryptographic Applications
• 13 Quadratic Reciprocity
• 14 Primality and Factorization
• 15 Geometry of Numbers
• 16 Arithmetic Functions
• 17 Continued Fractions
• 18 Gaussian Integers
• 19 Algebraic Integers
• 20 The Distribution of Primes
• 21 Epilogue: Fermat’s Last Theorem
• A Supplementary Topics
• B Answers and Hints for Odd-Numbered Exercises
• Index