# Chapter 10: Number-Theoretic Algorithms ## Overview Suppose Bob wants to send Alice a secret love note over the Internet, but he is afraid some of his friends might intercept the message and read it. If he could encode the message so that it appears as gibberish and only Alice could decode the gibberish back to the original message, he would not need to fear his friends intercepting the message. Number-theoretic algorithms can help Bob develop a system for doing this. We discuss such algorithms next. ***Number theory*** is the branch of mathematics concerned with the properties of the integers. *Number-theoretic algorithms* are algorithms that solve problems involving the integers. For example, a number-theoretic algorithm might find the greatest common divisor of two integers. After reviewing basic number theory in [Section 10.1](LiB0081.html#993), we present Euclid's algorithm for finding the greatest common divisor in [Section 10.2](LiB0082.html#1029). Next, [Section 10.3](LiB0083.html#1049) reviews modular arithmetic, [Section 10.4](LiB0085.html#1129) shows an algorithm for solving modular linear equations, and [Section 10.5](LiB0086.html#1138) develops an algorithm for computing modular powers. [Section 10.6](LiB0087.html#1200) concerns algorithms for determining whether a number is prime. An important application of number-theoretic algorithms is in ***cryptography***, which is the discipline concerned with encrypting a message sent from one party to another, so that someone who intercepts the message will not be able to decode it. In [Section 10.7](LiB0087.html#1201) we present the Rivest-Shamir-Adelman (RSA) public-key cryptosystem, which is a system that does this. Before proceeding, we note that in this chapter we revert back to developing algorithms as we did in [Chapters 2](LiB0014.html#141) through [6](LiB0047.html#565). However, unlike the methods presented in those chapters, number-theoretic algorithms are concerned with solving a certain type of problem (namely ones involving the integers); they are not algorithms that share a common technique.