# Get PDF Primality Testing in Polynomial Time: From Randomized Algorithms to PRIMES Is in P

We start with the classical Euclidean Algorithm, formulated in the simplest way. There are other formulations, notably ones that use recursion. Fundamentals from Number Theory Algorithm 3. Lines 4 and 5 form a loop.

## PRIMES is in P little FAQ

In each iteration of the loop the remainder a mod b is computed and placed into b as the divisor in the next iteration ; simultaneously, the old value of b is put into a. In this way, the algorithm generates a sequence a0 , b0 , a1 , b1 ,. For an example, consider Table 3. The numbers ai and bi are the contents of variables a and b after the loop has been executed i times.

The value returned is We will see in a moment that this i 0 1 2 3 4 5 6 7 ai 46 bi 46 0 Table 3. Indeed, it is not hard to see that the Euclidean Algorithm always returns the value gcd n, m , for integers n and m. Lemma 3. If both m and n are 0, the value returned is also 0. Thus assume that n and m are not both 0.

### Table of contents

It will turn out that it has a running time linear in the number of bits of the input numbers in terms of arithmetic operations and quadratic cost in terms of bit operations. In fact, the cost is not more than that of multiplying m and n in binary by the naive method. This means that on a computer the Euclidean Algorithm can be carried out very quickly for numbers that have hundreds of bits, and in reasonable time even if they have thousands of bits. Assume Algorithm 3. A closer look reveals that the decrease is quite fast. We have noted in Proposition 3. In our example from Table 3.

Slightly extending the Euclidean Algorithm helps. Algorithm 3. But an additional quadruple of numbers is carried along in variables xa, ya, xb, yb. These variables are initialized in lines 3 and 5 and change in parallel with a and b in the body of the loop.

Finally, in line 10 the contents of xa and ya are returned along with gcd n, m. Let xa,i , ya,i , xb,i , yb,i denote the contents of the variables xa, ya, xb, yb after the loop in lines 6—9 has been carried out i times. Table 3. The following lemma states that the result of the Extended Euclidean Algorithm always has this property.

For the induction step, assume 3. As for the cost in terms of bit operations, we note without proof that the number of bit operations is bounded by O log n log m just as in the case of the simple Euclidean Algorithm. We want to say that looking at an integer a we are not really interested in a but only in the remainder a mod m. Congruence modulo m is an equivalence relation, i. As an example, we consider the multiplicative rule. We will use it without further comment by freely substituting equivalent terms in calculations.

Using Lemma 3. Like all equivalence relations, congruence modulo m splits its ground set Z into equivalence classes or congruence classes. We introduce an arithmetic structure on these classes. The subscript m at the operation symbols is omitted if no confusion arises. The proofs of these rules all follow the same pattern, namely one shows that the expressions involved are congruent modulo m, and then concludes that their remainders are equal. For example, the distributivity law c is proved as follows: Using Lemma 3.

But note the following cancellation rule. Since m divides ab by assumption, a must divide b. Remainders of 0, 1,. Theorem 3. Since n1 and n2 are relatively prime, we conclude by Proposition 3. By Lemma 3. The other half, concerning n2 , a2 , b2 , is proved in the same way. Further, we will often use it in the following form. By Theorem 3. Uniqueness follows from the fact that all solutions a to 3. Fundamentals from Number Theory The isomorphism properties are easily checked, just as in the case with two factors. For example, in Table 3.

For both directions, we intensively use Proposition 3. By Corollary 3. Using Corollary 3. In particular, we state and prove the fundamental theorem of arithmetic, which says that every positive integer can be written as a product of prime numbers in a unique way. The reader is invited to check that the number of rounds in the procedure just described cannot be larger than log n.

The venerable theorem noted next was proved by Euclid. Let p1 ,. Fundamentals from Number Theory It is not very hard to see that the numbers that are left unmarked are exactly the prime numbers in the interval [2, n]. When j attains the value p, this prime number turns out to be unmarked, and the number k becomes marked as the multiple sp of p. A slightly more elaborate version of the Sieve of Eratosthenes, given next, even marks each composite number in [2, n] with its smallest prime divisor. If m[j] turns out to be nonzero when j has value j, then in the i-loop lines 7—9 the unmarked multiples of j are marked with j.

From the algorithm it is then obvious that in the iteration of the j-loop lines 4—10 in which the variable j contains p the array component m[k] will be assigned the value p.

In the next round the following multiples of 7 are marked with 7: 49, 77, 91, , , , , , , Then the following multiples of 11 with 11 : , , , , This creates the list in Table 3. Note that for the numbers a that do not occur in the list, i. It says that every positive integer has one and only one prime decomposition.

Because this result is basic for everything that follows, we give a proof. We start with a lemma that says that a prime decomposition exists. Although we have just seen that this can be deduced by extending the Sieve of Eratosthenes method, we give a short, abstract proof. This is proved by induction on n. We may assume that p1 3. Fundamentals from Number Theory Proof. If p1 ,. For each pi we have the following: By Lemma 3. Suppose a prime number p occurred in both prime decompositions.

Then p would divide both n and m, hence gcd n, m would be larger than 1. Then there is a prime number p that divides gcd n, m and hence divides both n and m. We apply Corollary 3. We want to estimate how many primes there are up to some bound x. Fundamentals from Number Theory Theorem 3. In general, doubling the number of digits will approximately halve the percentage of prime numbers.

Readers who wish to see a full proof of the prime number theorem are referred to [6]; for details on the quality of the approximation see [16]. We cannot prove the prime number theorem here, and really we do not need it. We will have the opportunity to use a variant of these bounds Proposition 3. Moreover, lower bounds on the density of the prime numbers are important for analyzing the running time of randomized procedures for generating large prime numbers. Proof of Theorem 3. In2ncomparison to 2n the numis very large, namely very close to 2. Now consider the prime ber 2n n decomposition 3.

First, we orient ourselves about the order of magnitude of 2n n. We have 2n p m where the product extends over all prime factors of m. Interestingly, it is almost trivial to calculate to which power a prime divides the number n!. The proof is a typical example for a simple, but very helpful counting technique used a lot in combinatorics as well as in the amortized analysis of algorithms. We obtain 48 3. By Lemma A. The primes that occur in this factorization are factors of 2n!

From the previous lemma we get that each factor pks s is bounded by 2n. We combine Lemma 3. To see this, consider that inequality A. Indeed, in the rightmost fraction in 3. An upper bound for bm is obtained as follows: We know see A. Hence bm Now we may prove the claimed inequality by induction on N. Case 2: N is odd. For larger k, we proceed by induction. Combining this with 3. Substituting this into 3. Basics from Algebra: Groups, Rings, and Fields In this chapter we develop basic algebraic notions and facts to the extent needed for the applications in this book.

Equally important are the examples for such structures from number theory. At the center of attention are basic facts from group theory, especially about cyclic groups, which are central in the analysis of the deterministic primality test. We discuss commutative rings with 1 , with the central example being Zm.

Examples of binary operations are the addition and the multiplication operation on the set of positive integers or on the set Z. In particular, G is not empty. In view of the associative law, we can put parentheses at any place we want in expressions involving elements a1 ,. Groups are abundant in mathematics and in computer science. Here are a few examples.

Operation table of a group. We remark that there are many extremely important groups in mathematics and in application areas that are not commutative in the sense that 4. For example, in Example 4. In this book, though, we will be dealing exclusively with groups in which such a thing does not occur. The groups from Example 4. Proposition 4. Notation: In the situation of Example 4. In contrast, mZ is a subgroup of nZ if and only if n m. For this, we provide an easy-to-apply criterion. Lemma 4. A subgroup H splits the elements of a group G into disjoint classes. Let H be a subgroup of a group G.

We mention two examples. The equivalence classes are just the classes of numbers that are congruent modulo m. Let C1 ,. By Lemma 4. It is a matter of routine to establish the usual laws of calculating with exponents. Now we turn to the case of negative exponents. Because they are so natural, the rules listed in Lemma 4. In fact, it is the smallest subgroup of G with this property. It is called the subgroup generated by a. Example 4. A group operation table of a cyclic group. Basics from Algebra: Groups, Rings, and Fields where i is the imaginary unit.

If C is depicted as the Euclidean plane, the set Ur appears as an equidistant grid of r points on the unit circle, containing 1. We shall see later that all cyclic groups of size r are isomorphic; thus, the depiction given in Fig. By Proposition 4. Theorem 4.

## AKS primality test

Apply Proposition 4. We will see that indeed there is exactly one subgroup of size d for each divisor d of m. It is a simple consequence of the subgroup criterion Lemma 4. This yields the subgroups shown in Table 4. In particular, M is not empty. The neutral element is the number 0.

Note that also the set N with the multiplication operation is a monoid, with neutral element 1. In this text, we are dealing exclusively with commutative rings with 1. For convenience, we call these structures simply rings. The straightforward proofs are left to the reader. Here, we do not prove these rules systematically, but simply use them. We illustrate these observations by little numerical examples.

To close the section, we note that monoids really are the natural structures in which to carry out fast exponentiation. We use Algorithm 2. Of course, if the elements of M are structured elements like polynomials , then the total cost of carrying out Algorithm 4. A generating element g of this group is called a generator for F. Thus, 2 is a primitive element modulo Now reduce these fractions to lowest terms, by dividing numerator and denominator by their greatest common divisor: 1 1 1 1 5 1 7 2 3 5 11 1 12 , 6 , 4 , 3 , 12 , 2 , 12 , 3 , 4 , 6 , 12 , 1 , and group them according to their denominators: 1 1; 1 2; 1 2 3, 3; 1 3 4, 4; 1 5 6, 6; 1 5 7 11 12 , 12 , 12 , More generally, we can show the corresponding statement for every number n in place of Corollary 4.

The error analysis employs simple group theory and the Chinese Remainder Theorem. By Theorem 4. We then call 2 a Fermat witness for n more exactly, a witness for the fact that n is composite. As far as one can tell from looking at the value mod , there is no indication that is not prime. For much more information on composite numbers for which 2 is an F-liar [so-called pseudoprimes base 2], see [33]. Lemma 5. Unfortunately, for many composite numbers n this set is very slim. Just assume that n is a product of two distinct primes p and q.

Table 5. In this example there are some more F-witnesses than F-liars. Further, it is clear that if the algorithm outputs 1, then it has detected an F-witness a for n, hence n is guaranteed to be composite. With a little group theory it is easy to see that for many composite numbers n there will be an abundance of F-witnesses, so that this simple test will succeed with constant probability.

Theorem 5.

- Borges on Writing.
- Primality Proving A polynomial-time algorithm;
- Primality testing.
- The Biggest Loser Dessert Cookbook: More than 80 Healthy Treats That Satisfy Your Sweet Tooth without Breaking Your Calorie Budget;
- Survival, Evasion and Recovery: Multiservice Procedures For Survival, Evasion, And Recovery.

In Lemma 5. Namely, by Proposition 4. More convincing success probabilities may be obtained by repeating the Fermat test, as described next. Algorithm 5. Turned the other way round, if n is prime the output is guaranteed to be 0. For details see [17] and [14]. This bound is annoyingly close to 1 if n has only few and large prime factors. This is unfeasible as soon as p0 has more than 20 decimal digits, say. Thus for a reliable primality test that works for all composite numbers, we have to go beyond the Fermat test.

Before we formulate this more clever test, we state and prove a basic property of Carmichael numbers. If n is a Carmichael number, then n is a product of at least three distinct prime factors. We prove the contraposition: Assume that n is not a product of three or more distinct primes. For this, we consider two cases. Next we show that a is an F-witness for n. We know by Theorem 4. By the Chinese Remainder Theorem 3. Instead, we go back to the Fermat test. Of course, we are only interested in odd numbers n.

In Table 5. In contrast, 7, 32, 49, , , and are all F-liars for Calculating mod with two intermediate steps leads us to detect that 51 is a nontrivial square root of 1, which proves that is not prime. Similarly, the calculation with base reveals that is a nontrivial square root of 1. What can the sequence b0 ,. All possible patterns are depicted in Table 5. We distinguish four cases: 80 5. Thus n is composite in this case. Note that, surprisingly, the value of bk becomes irrelevant when these two cases are combined. Later, Miller [29] used the criterion in his deterministic algorithm that will have polynomial running time if the Extended Riemann Hypothesis ERH, a number- 5.

He showed that, assuming the ERH, the smallest A-witness for a composite number n will be of size O ln n 2. Later, Bach [8] gave an explicit bound of 2 ln n 2 for the smallest A-witness. The algorithm uses O log n 3 arithmetic operations, but its correctness hinges on the correctness of the ERH.

We next describe the randomized version of the compositeness test based on the concept of an A-witness, now commonly called the Miller-Rabin test. Exploiting the fact that n is represented in binary in a typical computer makes it possible to speed this part up by using shifts of binary words instead of divisions. The calculation of au mod n by fast exponentiation in line 3 takes O log n arithmetic operations and O log n 3 naive implementation of multiplication and division resp.

Overall, the algorithm uses O log n arithmetic operations and O log n 3 resp. We now turn to studying the output behavior. If the Miller-Rabin test yields output 1, then n is composite.

## Primality Test

The Miller-Rabin Test Proof. Let a be the element chosen in the algorithm, and assume that the output is 1. We show that a is an A-witness for n. By Lemma 5. There are two ways for the output 1 to occur. This entails that b0 ,. Case b : Line 9 is executed. Again, a is an A-witness. We show that the probability that Algorithm 5. In order to bound the number of A-liars, we would like to proceed as in the proof of Theorem 5.

Unfortunately, the set of A-liars need not be a subgroup. If n is not a Carmichael number, this approach is easy to realize. From here on, let us assume that n is a Carmichael number. Now 5. The Miller-Rabin Test and 5. For the purpose of this illustration it is not relevant that is not a Carmichael number. Going back to Table 5. We have shown an error bound of 12 for the Miller-Rabin algorithm.

We summarize: Proposition 5. Historically, it predates the Miller-Rabin test. Like the Miller-Rabin test it is a randomized procedure; it is capable of recognizing composite numbers with a probability of at least It is clear that being a quadratic residue or not is a property of the congruence class of a. Example 6. If we square the numbers 1,. On the other hand, the squares of 1,. We calculate in this group. Lemma 6. For example, 12 is a quadratic residue modulo 13, while 10 is a nonresidue modulo However, as it turns out, such a generalization would not have nice arithmetic and algorithmic properties.

If n happens to be a prime number, then the Jacobi symbol na is just the same as the Legendre symbol, so it is harmless that we use the same notation for both. Interesting values occur only if a and n are 88 6. Parts a and b follow by applying Lemma 6. We apply Lemma 6. For example, the entries in row column 27 are identical to those in row column 3. Kanpur, India: Indian Institute of Technology, Knuth, D. The Art of Computer Programming, Vol. Reading, MA: Addison-Wesley, Martin, M. Pomerance, C. Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed.

Robinson, S. A16, August 8, Wagon, S. Mathematica in Action. New York: W. Freeman, pp. Weisstein, E. Williams, H. Edouard Lucas and Primality Testing. New York: Wiley, Prime Numbers and Computer Methods for Factorization, 2nd ed. Robinson, S. A16, August 8, Wagon, S. Mathematica in Action. New York: W. Freeman, pp. Weisstein, E. Williams, H. Edouard Lucas and Primality Testing. New York: Wiley, Weisstein, Eric W. Explore thousands of free applications across science, mathematics, engineering, technology, business, art, finance, social sciences, and more. Walk through homework problems step-by-step from beginning to end.

Hints help you try the next step on your own. Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet. Collection of teaching and learning tools built by Wolfram education experts: dynamic textbook, lesson plans, widgets, interactive Demonstrations, and more.