Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

9.3 Primality Testing

Suppose we have an integer of 300 digits that we want to test for primality. We know by Exercise 7 in Chapter 3 that one way is to divide by all the primes up to its square root. What happens if we try this? There are around $3 \times 10^{147}$ $3 \times 10^{147}$ primes less than $10^{150}$ $10^{150}$ . This is significantly more than the number of particles in the universe. Moreover, if the computer can handle $10^{10}$ $10^{10}$ primes per second, the calculation would take around $3 \times 10^{130}$ $3 \times 10^{130}$ years. (It’s been suggested that you could go sit on the beach for 20 years, then buy a computer that is 1000 times faster, which would cut the runtime down to $3 \times 10^{127}$ $3 \times 10^{127}$ years – a very large savings!) Clearly, better methods are needed. Some of these are discussed in this section.

A very basic idea, one that is behind many factorization methods, is the following.

Basic Principle

Let $n$ $n$ be an integer and suppose there exist integers $x$ $x$ and $y$ $y$ with $x^{2} \equiv y^{2} (mod n)$ $x^{2} \equiv y^{2} (mod n)$ , but $x \equiv \pm y (mod n)$ $x \equiv \pm y (mod n)$ . Then $n$ $n$ is composite. Moreover, $gcd (x - y, n)$ $gcd (x - y, n)$ gives a nontrivial factor of $n$ $n$ .

Proof. Let $d = gcd (x - y, n)$ $d = gcd (x - y, n)$ . If $d = n$ $d = n$ then $x \equiv y (mod n)$ $x \equiv y (mod n)$ , which is assumed not to happen. Suppose $d = 1$ $d = 1$ . The Proposition in Subsection 3.3.1 says that if $a b \equiv a c (mod n)$ $a b \equiv a c (mod n)$ and if $gcd (a, n) = 1$ $gcd (a, n) = 1$ , then $b \equiv c (mod n)$ $b \equiv c (mod n)$ . In our case, let $a = x - y$ $a = x - y$ , let $b = x + y$ $b = x + y$ , and let $c = 0$ $c = 0$ . Then $a b = x^{2} - y^{2} \equiv 0 \equiv a c$ $a b = x^{2} - y^{2} \equiv 0 \equiv a c$ . If $d = gcd (x - y, n) = 1$ $d = gcd (x - y, n) = 1$ , then $x + y = b \equiv c = 0$ $x + y = b \equiv c = 0$ . This says that $x \equiv - y (mod n)$ $x \equiv - y (mod n)$ , which contradicts the assumption that $x \equiv - y (mod n)$ $x \equiv - y (mod n)$ . Therefore, $d \neq 1, n$ $d \neq 1, n$ , so $d$ $d$ is a nontrivial factor of $n$ $n$ .

Example

Since $12^{2} \equiv 2^{2} (mod 35)$ $12^{2} \equiv 2^{2} (mod 35)$ , but $12 \equiv \pm 2 (mod 35),$ $12 \equiv \pm 2 (mod 35),$ , we know that 35 is composite. Moreover, $gcd (12 - 2, 35) = 5$ $gcd (12 - 2, 35) = 5$ is a nontrivial factor of 35.

It might be surprising, but factorization and primality testing are not the same. It is much easier to prove a number is composite than it is to factor it. There are many large integers that are known to be composite but that have not been factored. How can this be done? We give a simple example. We know by Fermat’s theorem that if $p$ $p$ is prime, then $2^{p - 1} \equiv 1 (mod p)$ $2^{p - 1} \equiv 1 (mod p)$ . Let’s use this to show 35 is not prime. By successive squaring, we find (congruences are mod 35)

\begin{array}{l} 2^{4} \equiv 16, \\ 2^{8} \equiv 256 \equiv 11 \\ 2^{16} \equiv 121 \equiv 16 \\ 2^{32} \equiv 256 \equiv 11. \end{array}

$\begin{array}{l} 2^{4} \equiv 16, \\ 2^{8} \equiv 256 \equiv 11 \\ 2^{16} \equiv 121 \equiv 16 \\ 2^{32} \equiv 256 \equiv 11. \end{array}$

Therefore,

2^{34} \equiv 2^{32} 2^{2} \equiv 11 \cdot 4 \equiv 9 \equiv 1 (mod 35) .

$2^{34} \equiv 2^{32} 2^{2} \equiv 11 \cdot 4 \equiv 9 \equiv 1 (mod 35) .$

Fermat’s theorem says that 35 cannot be prime, so we have proved 35 to be composite without finding a factor.

The same reasoning gives us the following.

Fermat Primality Test

Let $n > 1$ $n > 1$ be an integer. Choose a random integer $a$ $a$ with $1 < a < n - 1$ $1 < a < n - 1$ . If $a^{n - 1} \equiv 1 (mod n)$ $a^{n - 1} \equiv 1 (mod n)$ , then $n$ $n$ is composite. If $a^{n - 1} \equiv 1 (mod n)$ $a^{n - 1} \equiv 1 (mod n)$ , then $n$ $n$ is probably prime.

Although this and similar tests are usually called “primality tests,” they are actually “compositeness tests,” since they give a completely certain answer only in the case when $n$ $n$ is composite. The Fermat test is quite accurate for large $n$ $n$ . If it declares a number to be composite, then this is guaranteed to be true. If it declares a number to be probably prime, then empirical results show that this is very likely true. Moreover, since modular exponentiation is fast, the Fermat test can be carried out quickly.

Recall that modular exponentiation is accomplished by successive squaring. If we are careful about how we do this successive squaring, the Fermat test can be combined with the Basic Principle to yield the following stronger result.

Miller-Rabin Primality Test

Let $n > 1$ $n > 1$ be an odd integer. Write $n - 1 = 2^{k} m$ $n - 1 = 2^{k} m$ with $m$ $m$ odd. Choose a random integer $a$ $a$ with $1 < a < n - 1$ $1 < a < n - 1$ . Compute $b_{0} \equiv a^{m} (mod n)$ $b_{0} \equiv a^{m} (mod n)$ . If $b_{0} \equiv \pm 1 (mod n)$ $b_{0} \equiv \pm 1 (mod n)$ , then stop and declare that $n$ $n$ is probably prime. Otherwise, let $b_{1} \equiv b_{0}^{2} (mod n)$ $b_{1} \equiv b_{0}^{2} (mod n)$ . If $b_{1} \equiv 1 (mod n)$ $b_{1} \equiv 1 (mod n)$ , then $n$ $n$ is composite (and $gcd (b_{0} - 1, n)$ $gcd (b_{0} - 1, n)$ gives a nontrivial factor of $n$ $n$ ). If $b_{1} \equiv - 1 (mod n)$ $b_{1} \equiv - 1 (mod n)$ , then stop and declare that $n$ $n$ is probably prime. Otherwise, let $b_{2} \equiv b_{1}^{2} (mod n)$ $b_{2} \equiv b_{1}^{2} (mod n)$ . If $b_{2} \equiv 1 (mod n)$ $b_{2} \equiv 1 (mod n)$ , then $n$ $n$ is composite. If $b_{2} \equiv - 1 (mod n)$ $b_{2} \equiv - 1 (mod n)$ , then stop and declare that $n$ $n$ is probably prime. Continue in this way until stopping or reaching $b_{k - 1}$ $b_{k - 1}$ . If $b_{k - 1} \equiv - 1 (mod n)$ $b_{k - 1} \equiv - 1 (mod n)$ , then $n$ $n$ is composite.

Example

Let $n = 561$ $n = 561$ . Then $n - 1 = 560 = 16 \cdot 35$ $n - 1 = 560 = 16 \cdot 35$ , so $2^{k} = 2^{4}$ $2^{k} = 2^{4}$ and $m = 35$ $m = 35$ . Let $a = 2$ $a = 2$ . Then

\begin{array}{rcl} b_{0} & \equiv & 2^{35} \equiv 263 (mod 561) \\ b_{1} & \equiv & b_{0}^{2} \equiv 166 (mod 561) \\ b_{2} & \equiv & b_{1}^{2} \equiv 67 (mod 561) \\ b_{3} & \equiv & b_{2}^{2} \equiv 1 (mod 561) . \end{array}

$\begin{array}{rcl} b_{0} & \equiv & 2^{35} \equiv 263 (mod 561) \\ b_{1} & \equiv & b_{0}^{2} \equiv 166 (mod 561) \\ b_{2} & \equiv & b_{1}^{2} \equiv 67 (mod 561) \\ b_{3} & \equiv & b_{2}^{2} \equiv 1 (mod 561) . \end{array}$

Since $b_{3} \equiv 1 (mod 561)$ $b_{3} \equiv 1 (mod 561)$ , we conclude that 561 is composite. Moreover, $gcd (b_{2} - 1, 561) = 33$ $gcd (b_{2} - 1, 561) = 33$ , which is a nontrivial factor of 561.

If $n$ $n$ is composite and $a^{n - 1} \equiv 1 (mod n)$ $a^{n - 1} \equiv 1 (mod n)$ , then we say that $n$ $n$ is a pseudoprime for the base $a$ $a$ . If $a$ $a$ and $n$ $n$ are such that $n$ $n$ passes the Miller-Rabin test, we say that $n$ $n$ is a strong pseudoprime for the base $a$ $a$ . We showed in Section 3.6 that $2^{560} \equiv 1 (mod 561)$ $2^{560} \equiv 1 (mod 561)$ , so 561 is a pseudoprime for the base 2. However, the preceding calculation shows that 561 is not a strong pseudoprime for the base 2. For a given base, strong pseudoprimes are much more rare than pseudoprimes.

Up to $10^{10}$ $10^{10}$ , there are 455052511 primes. There are 14884 pseudoprimes for the base 2, and 3291 strong pseudoprimes for the base 2. Therefore, calculating $2^{n - 1} (mod n)$ $2^{n - 1} (mod n)$ will fail to recognize a composite in this range with probability less than 1 out of 30 thousand, and using the Miller-Rabin test with $a = 2$ $a = 2$ will fail with probability less than 1 out of 100 thousand.

It can be shown that the probability that the Miller-Rabin test fails to recognize a composite for a randomly chosen $a$ $a$ is at most $1 / 4$ $1 / 4$ . In fact, it fails much less frequently than this. See [Damgå rd et al.]. If we repeat the test 10 times, say, with randomly chosen values of $a$ $a$ , then we expect that the probability of certifying a composite number as prime is at most $(1 / 4)^{10} ≃ 10^{- 6}$ $(1 / 4)^{10} ≃ 10^{- 6}$ . In practice, using the test for a single $a$ $a$ is fairly accurate.

Though strong pseudoprimes are rare, it has been proved (see [Alford et al.]) that, for any finite set $B$ $B$ of bases, there are infinitely many integers that are strong pseudoprimes for all $b \in B$ $b \in B$ . The first strong pseudoprime for all the bases $b = 2, 3, 5, 7$ $b = 2, 3, 5, 7$ is 3215031751. There is a 337-digit number that is a strong pseudoprime for all bases that are primes $< 200$ $< 200$ .

Suppose we need to find a prime of around 300 digits. The prime number theorem asserts that the density of primes around $x$ $x$ is approximately $1 / ln x$ $1 / ln x$ . When $x = 10^{300}$ $x = 10^{300}$ , this gives a density of around $1 / ln (10^{300}) = 1 / 690$ $1 / ln (10^{300}) = 1 / 690$ . Since we can skip the even numbers, this can be raised to $1 / 345$ $1 / 345$ . Pick a random starting point, and throw out the even numbers (and multiples of other small primes). Test each remaining number in succession by the Miller-Rabin test. This will tend to eliminate all the composites. On average, it will take less than 400 uses of the Miller-Rabin test to find a likely candidate for a prime, so this can be done fairly quickly. If we need to be completely certain that the number in question is prime, there are more sophisticated primality tests that can test a number of 300 digits in a few seconds.

Why does the test work? Suppose, for example, that $b_{3} \equiv 1 (mod n)$ $b_{3} \equiv 1 (mod n)$ . This means that $b_{2}^{2} \equiv 1^{2} (mod n)$ $b_{2}^{2} \equiv 1^{2} (mod n)$ . Apply the Basic Principle from before. Either $b_{2} \equiv \pm 1 (mod n)$ $b_{2} \equiv \pm 1 (mod n)$ , or $b_{2} \equiv \pm 1 (mod n)$ $b_{2} \equiv \pm 1 (mod n)$ and $n$ $n$ is composite. In the latter case, $gcd (b_{2} - 1, n)$ $gcd (b_{2} - 1, n)$ gives a nontrivial factor of $n$ $n$ . In the former case, the algorithm would have stopped by the previous step. If we reach $b_{k - 1}$ $b_{k - 1}$ , we have computed $b_{k - 1} \equiv a^{(n - 1) / 2} (mod n)$ $b_{k - 1} \equiv a^{(n - 1) / 2} (mod n)$ . The square of this is $a^{n - 1}$ $a^{n - 1}$ , which must be $1 (mod n)$ $1 (mod n)$ if $n$ $n$ is prime, by Fermat’s theorem. Therefore, if $n$ $n$ is prime, $b_{k - 1} \equiv \pm 1 (mod n)$ $b_{k - 1} \equiv \pm 1 (mod n)$ . All other choices mean that $n$ $n$ is composite. Moreover, if $b_{k - 1} \equiv 1$ $b_{k - 1} \equiv 1$ , then, if we didn’t stop at an earlier step, $b_{k - 2}^{2} \equiv 1^{2} (mod n)$ $b_{k - 2}^{2} \equiv 1^{2} (mod n)$ with $b_{k - 2} \equiv \pm 1 (mod n)$ $b_{k - 2} \equiv \pm 1 (mod n)$ . This means that $n$ $n$ is composite (and we can factor $n$ $n$ ).

In practice, if $n$ $n$ is composite, usually we reach $b_{k - 1}$ $b_{k - 1}$ and it is not $\pm 1 (mod n)$ $\pm 1 (mod n)$ . In fact, usually $a^{n - 1} \equiv 1 (mod n)$ $a^{n - 1} \equiv 1 (mod n)$ . This means that Fermat’s test says $n$ $n$ is not prime.

For example, let $n = 299$ $n = 299$ and $a = 2$ $a = 2$ . Since $2^{298} \equiv 140 (mod 299)$ $2^{298} \equiv 140 (mod 299)$ , Fermat’s theorem and also the Miller-Rabin test say that 299 is not prime (without factoring it). The reason this happens is the following. Note that $299 = 13 \times 23$ $299 = 13 \times 23$ . An easy calculation shows that $2^{12} \equiv 1 (mod 13)$ $2^{12} \equiv 1 (mod 13)$ and no smaller exponent works. In fact, $2^{j} \equiv 1 (mod 13)$ $2^{j} \equiv 1 (mod 13)$ if and only if $j$ $j$ is a multiple of 12. Since 298 is not a multiple of 12, we have $2^{298} \equiv 1 (mod 13)$ $2^{298} \equiv 1 (mod 13)$ , and therefore also $2^{298} \equiv 1 (mod 299)$ $2^{298} \equiv 1 (mod 299)$ . Similarly, $2^{j} \equiv 1 (mod 23)$ $2^{j} \equiv 1 (mod 23)$ if and only if $j$ $j$ is a multiple of 11, from which we can again deduce that $2^{298} \equiv 1 (mod 299)$ $2^{298} \equiv 1 (mod 299)$ . If Fermat’s theorem (and the Miller-Rabin test) were to give us the wrong answer in this case, we would have needed $13 \cdot 23 - 1$ $13 \cdot 23 - 1$ to be a multiple of $12 \cdot 11$ $12 \cdot 11$ .

Consider the general case $n = p q$ $n = p q$ , a product of two primes. For simplicity, consider the case where $p > q$ $p > q$ and suppose $a^{k} \equiv 1 (mod p)$ $a^{k} \equiv 1 (mod p)$ if and only if $k \equiv 0 (mod p - 1)$ $k \equiv 0 (mod p - 1)$ . This means that $a$ $a$ is a primitive root mod $p$ $p$ ; there are $ϕ (p - 1)$ $ϕ (p - 1)$ such $a$ $a$ mod $p$ $p$ . Since $0 < q - 1 < p - 1$ $0 < q - 1 < p - 1$ , we have

n - 1 \equiv p q - 1 \equiv q (p - 1) + q - 1 \equiv 0 (mod p - 1) .

$n - 1 \equiv p q - 1 \equiv q (p - 1) + q - 1 \equiv 0 (mod p - 1) .$

Therefore, $a^{n - 1} \equiv 1 (mod p)$ $a^{n - 1} \equiv 1 (mod p)$ by our choice of $a$ $a$ , which implies that $a^{n - 1} \equiv 1 (mod n)$ $a^{n - 1} \equiv 1 (mod n)$ . Similar reasoning shows that usually $a^{n - 1} \equiv 1 (mod n)$ $a^{n - 1} \equiv 1 (mod n)$ for many other choices of $a$ $a$ , too.

But suppose we are in a case where $a^{n - 1} \equiv 1 (mod n)$ $a^{n - 1} \equiv 1 (mod n)$ . What happens? Let’s look at the example of $n = 561$ $n = 561$ . Since $561 = 3 \times 11 \times 17$ $561 = 3 \times 11 \times 17$ , we consider what is happening to the sequence $b_{0}, b_{1}, b_{2}, b_{3}$ $b_{0}, b_{1}, b_{2}, b_{3}$ mod 3, mod 11, and mod 17:

\begin{array}{l} b_{0} & \equiv & - 1 & (\mod 3), & \equiv & - 1 & (\mod 11), & \equiv & 8 & (\mod 17), \\ b_{1} & \equiv & 1 & (\mod 3), & \equiv & 1 & (\mod 11), & \equiv & - 4 & (\mod 17), \\ b_{2} & \equiv & 1 & (\mod 3), & \equiv & 1 & (\mod 11), & \equiv & - 1 & (\mod 17), \\ b_{3} & \equiv & 1 & (\mod 3), & \equiv & 1 & (\mod 11), & \equiv & 1 & (\mod 17) . \end{array}

$\begin{array}{l} b_{0} & \equiv & - 1 & (\mod 3), & \equiv & - 1 & (\mod 11), & \equiv & 8 & (\mod 17), \\ b_{1} & \equiv & 1 & (\mod 3), & \equiv & 1 & (\mod 11), & \equiv & - 4 & (\mod 17), \\ b_{2} & \equiv & 1 & (\mod 3), & \equiv & 1 & (\mod 11), & \equiv & - 1 & (\mod 17), \\ b_{3} & \equiv & 1 & (\mod 3), & \equiv & 1 & (\mod 11), & \equiv & 1 & (\mod 17) . \end{array}$

Since $b_{3} \equiv 1 (mod 561)$ $b_{3} \equiv 1 (mod 561)$ , we have $b_{2}^{2} \equiv b_{3} \equiv 1$ $b_{2}^{2} \equiv b_{3} \equiv 1$ mod all three primes. But there is no reason that $b_{3}$ $b_{3}$ is the first time we get $b_{i} \equiv 1$ $b_{i} \equiv 1$ mod a particular prime. We already have $b_{1} \equiv 1$ $b_{1} \equiv 1$ mod 3 and mod 11, but we have to wait for $b_{3}$ $b_{3}$ when working mod 17. Therefore, $b_{2}^{2} \equiv b_{3} \equiv 1$ $b_{2}^{2} \equiv b_{3} \equiv 1$ mod 3, mod 11, and mod 17, but $b_{2}$ $b_{2}$ is congruent to 1 only mod 3 and mod 11. Therefore, $b_{2} - 1$ $b_{2} - 1$ contains the factors 3 and 11, but not 17. This is why $gcd (b_{2} - 1, 561)$ $gcd (b_{2} - 1, 561)$ finds the factor 33 of 561. The reason we could factor 561 by this method is that the sequence $b_{0}, b_{1}, \dots$ $b_{0}, b_{1}, \dots$ reached 1 mod the primes not all at the same time.

More generally, consider the case $n = p q$ $n = p q$ (a product of several primes is similar) and suppose $a^{n - 1} \equiv 1 (mod n)$ $a^{n - 1} \equiv 1 (mod n)$ . As pointed out previously, it is very unlikely that this is the case; but if it does happen, look at what is happening mod $p$ $p$ and mod $q$ $q$ . It is likely that the sequences $b_{i} (mod p)$ $b_{i} (mod p)$ and $b_{i} (mod q)$ $b_{i} (mod q)$ reach $- 1$ $- 1$ and then 1 at different times, just as in the example of 561. In this case, we will be have $b_{i} \equiv - 1 (mod p)$ $b_{i} \equiv - 1 (mod p)$ but $b_{i} \equiv 1 (mod q)$ $b_{i} \equiv 1 (mod q)$ for some $i$ $i$ ; therefore, $b_{i}^{2} \equiv 1 (mod n)$ $b_{i}^{2} \equiv 1 (mod n)$ but $b_{i} \equiv \pm 1 (mod n)$ $b_{i} \equiv \pm 1 (mod n)$ . Therefore, we’ll be able to factor $n$ $n$ .

The only way that $n$ $n$ can pass the Miller-Rabin test is to have $a^{n - 1} \equiv 1 (mod n)$ $a^{n - 1} \equiv 1 (mod n)$ and also to have the sequences $b_{i} (mod p)$ $b_{i} (mod p)$ and $b_{i} (mod q)$ $b_{i} (mod q)$ reach 1 at the same time. This rarely happens.

Another primality test of a nature similar to the Miller-Rabin test is the following, which uses the Jacobi symbol (see Section 3.10).

Solovay-Strassen Primality Test

Let $n$ $n$ be an odd integer. Choose several random integers $a$ $a$ with $1 < a < n - 1$ $1 < a < n - 1$ . If

\begin{matrix} (\frac{a}{n}) \equiv a^{(n - 1) / 2} & (mod n) \end{matrix}

$\begin{matrix} (\frac{a}{n}) \equiv a^{(n - 1) / 2} & (mod n) \end{matrix}$

for some $a$ $a$ , then $n$ $n$ is composite. If

\begin{matrix} (\frac{a}{n}) \equiv a^{(n - 1) / 2} & (mod n) \end{matrix}

$\begin{matrix} (\frac{a}{n}) \equiv a^{(n - 1) / 2} & (mod n) \end{matrix}$

for all of these random $a$ $a$ , then $n$ $n$ is probably prime.

Note that if $n$ $n$ is prime, then the test will declare $n$ $n$ to be a probable prime. This is because of Part 2 of the second Proposition in Section 3.10.

The Jacobi symbol can be evaluated quickly, as in Section 3.10. The modular exponentiation can also be performed quickly.

For example,

\begin{matrix} (\frac{2}{15}) = - 1 \equiv 23 \equiv 2^{(15 - 1) / 2} & (mod 15), \end{matrix}

$\begin{matrix} (\frac{2}{15}) = - 1 \equiv 23 \equiv 2^{(15 - 1) / 2} & (mod 15), \end{matrix}$

so 15 is not prime. As in the Miller-Rabin tests, we usually do not get $\pm 1$ $\pm 1$ for $a^{(n - 1) / 2} (mod n)$ $a^{(n - 1) / 2} (mod n)$ . Here is a case where it happens:

\begin{matrix} (\frac{2}{341}) = - 1 \equiv + 1 \equiv 2^{(341 - 1) / 2} & (mod 341) . \end{matrix}

$\begin{matrix} (\frac{2}{341}) = - 1 \equiv + 1 \equiv 2^{(341 - 1) / 2} & (mod 341) . \end{matrix}$

However, the Solovay-Strassen test says that 341 is composite.

Both the Miller-Rabin and the Solovay-Strassen tests work quickly in practice, but, when $p$ $p$ is prime, they do not give rigorous proofs that $p$ $p$ is prime. There are tests that actually prove the primality of $p$ $p$ , but they are somewhat slower and are used only when it is essential that the number be proved to be prime. Most of these methods are probabilistic, in the sense that they work with very high probability in any given case, but success is not guaranteed. In 2002, Agrawal, Kayal, and Saxena [Agrawal et al.] gave what is known as a deterministic polynomial time algorithm for deciding whether or not a number is prime. This means that the computation time is always, rather than probably, bounded by a constant times a power of $log p$ $log p$ . This was a great theoretical advance, but their algorithm has not yet been improved to the point that it competes with the probabilistic algorithms.

For more on primality testing and its history, see [Williams].

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 9.3 Primality Testing

Create new playlist

Sign In

Sign Up

Table of Contents for
9.3 Primality Testing