tests for both these languages. Alas, we shall see in Section 11.5.5 that both the primes and the composite numbers axe in AfP. Since they are complements of each other, should either be NP-complete, it would follow that AfV = co-AfV, which we doubt is the case. Rirther, the fact that the set of primes is in UV means that if we could show the primes to be NP-complete then we could conclude TIP = AfV, another unlikely situation.

11.5.2 Introduction to Modular Arithmetic

Before looking at algorithms for recognizing the set of primes, we shall introduce some basic concepts regarding modular arithmetic, that is, the usual arithmetic operations executed modulo some integer, often a prime. Let p be any integer. The integers modulo p are 0,1,... ,p - 1.

We can define addition and multipUcation modulo p to apply only to this set of p integers by performing the ordinary calculation and then computing the remainder when the result is divided by p. Addition is quite straightforward, since the sum is either less than p, in which case we have nothing additional to do, or it is between p and 2p - 2, in which case we subtract p to get an integer in the range 0,1,... ,p - 1. Modular addition obeys the usual algebraic laws; it is commutative, associative, and has 0 as the identity. Subtraction is still the inverse of addition, and we can compute the modular difference x - у by subtracting as usual, and adding p if the result is below 0. The negation of x, which is -X, is the same as 0 - ж, just as in ordinary arithmetic. Thus, -0 - 0, and if X фО, then -x is the same asp - x.

Example 11.21: Suppose p = 13. Then 3 -b 5 = 8, and 7 + 10 = 4. To see the latter, note that in ordinary arithmetic, 7 + 10 - 17, which is not less than 13. We therefore subtract 13 to get the proper result, 4. The value of -5 modulo 13 is 13 - 5, or 8. The difference 11-4 modulo 13 is 7, while the difference 4 - 11 is 6. To see the latter, in ordinary arithmetic, 4 - 11 = -7, so we must add 13 to get 6. □

Multiplication modulo p is performed by multiplying as ordinary numbers, and then taking the remainder of the result divided by p. Multiplication also satisfies the usual algebraic laws; it is commutative and associative, 1 is the identity, 0 is the annihilator, and multiplication distributes over addition. However, division by nonzero values is trickier, and even the existence of inverses for integers modulo p depends on whether or not p is a prime. In general, if x is one of the integers modulo p, that is, 0 < i < p, then x~, or 1/x is that number if it exists, such that xy = 1 modulo p.

Example 11.22: In Fig. 11.9 we see the multiplication table for the nonzero integers modulo the prime 7. The entry in row i and column j is the product ij modulo 7. Notice that each of the nonzero integers has an inverse; 2 and 4 are each others inverses, so are 3 and 5, while 1 and 6 are their own inverses. That

Figure 11.9: Multiplication modulo 7

is, 2 X 4, 3 X 5, 1 X 1, and 6x6 are all 1. Thus, we can divide by any nonzero number x/y by computing y~ and then multiplying x x For instance, 3/4 = 3x4-1=3x2-6.

Figure 11.10: Multiplication modulo 6

Compare this situation with the multiplication table modulo 6. First, we observe that only 1 and 5 even have inverses; they are each their own inverse. Other numbers have no inverse. In addition, there are numbers that are not 0, but whose product is 0, such as 2 and 3. That situation never occurs for ordinary integer arithmetic, and it never happens when arithmetic is modulo a prime. □

There is another distinction between multiplication modulo a prime and modulo a composite number that turns out to be quite important for primality tests. The degree of a number a modulo p is the smallest positive power of a that is equal to 1. Some useful facts, which we shall not prove here are:

If p is a prune, then a = 1 modulo p. This statement is called Fermats theorem.

The degree of a modulo a prime p is always a divisor of p - 1.

If p is a prime, there is always some a that has degree p - 1 modulo p.

Do not confuse Fern:iats theorem with Fermats last theorem, which asserts the nonexistence of integer solutions to ж -b j/ - г for n > 3.

Example 11.23: Consider again the multiplication table modulo 7 in Fig. 11.9. The degree of 2 is 3, since 2 - 4, and 2 - 1. The degree of 3 is 6, since 3 = 2, 3 = 6, 3 = 4, 3 = 5, and 3 = 1. By similar calculations, we find that 4 has degree 3, 5 has degree 6, б has degree 2, and 1 has degree 1. □

11.5.3 The Complexity of Modular-Arithmetic Computations

Before proceeding to the applications of modular arithmetic to primality testing, we must establish some basic facts about the running time of the essential operations. Suppose we wish to compute modulo some prime p, and the binary representation of p is n bits long; i.e., p itself is around 2 . As always, the running tune of a computation is stated in terms of n, the input length, rather than p, the value of the input. For Instance, counting up to p takes time 0(2 ), so any computation that Involves p steps, will not be polynomial-time, as a function of n.

However, we can surely add two numbers modulo p in 0(n) tirne on a typical computer or multitape TM. Recall that we simply add the binary numbers, and if the result is p or greater, then subtract p. Likewise, we can multiply two numbers in O(n) time, either on a computer or a Turing machine. After multiplying the numbers in the ordinary way, and getting a result of at most 2n bits, we divide by p and take the remainder.

Raising a number x to an exponent is trickier, since that exponent may itself be exponential in n. As we shall see, an important step is raising x to the power p - 1. Since p - 1 is around 2 , if we were to multiply x by itself p - 2 times, we would need 0(2 ) multiplications, and even though each multiplication involved only n-bit numbers and could be carried out in O(n) time, the total time would be 0(n2 ), which is not polynomial in n.

Fortunately, there is a recursive-doubling trick that lets us compute x~ (or any other power of x up to p) in time that is polynomial in n:

1. Compute the at most n exponents x,x,x,x,... , until the exponent exceeds p - 1. Each value is an n-bit number that is computed in 0{n) time by squaring the previous value in the sequence, so the total work is 0(n3).

2. Find the binary representation of p - 1, say p - 1 = a i Oitto. We can write

p - 1 oo + 2oi +4a2 + -b 2 ы 1 where each aj is either 0 or 1. Therefore,

3.Р-1 Qo-H2Qi4-4a2+-+2 -Q ,

which is the product of those values x for which aj - 1. Suice we computed each of those x s in step (1), and each is an n-hit number, we can compute the product of these n or fewer numbers in O(n) time.