Miller-Rabin Algorithm, A Deterministic Primality Algorithm, Distribution of Primes

**TESTING FOR PRIMALITY**

For many cryptographic algorithms, it is necessary to select one or more very large prime numbers at random.
Thus, we are faced
with the task of determining whether a given large
number is prime.
There is no simple yet efficient means
of accomplishing this task.

In this section, we present one attractive and popular
algorithm. You may be surprised to
learn that this algorithm yields a
number that is not necessarily
a prime. However, the algorithm can yield a number that is almost
certainly a prime. This will be explained presently. We also make reference to a deterministic
algo- rithm for finding
primes. The section
closes with a discussion concerning the distri- bution
of primes.

Miller-Rabin
Algorithm

The algorithm due to Miller
and Rabin [MILL75,
RABI80] is typically used to test a
large number for primality. Before explaining the algorithm, we need some back-
ground. First, any positive odd integer *n *>= 3 can be expressed as

To see this, note
that *n *- 1 is an even integer. Then,
divide (*n *- 1) by 2 until the
result is an odd number
*q*, for a total
of *k *divisions. If *n *is expressed as a binary
num- ber, then the result is achieved by shifting the number to the right until the rightmost
digit is a 1, for a total of *k *shifts. We now develop
two properties of prime numbers that we will need.

*T**WO **P**ROPERTIES OF **P**RIME **N*** UMBERS **The

The **second property **is stated as follows:
Let *p *be a prime number greater than 2. We
can then write *p *- 1 = 2*k**q *with *k *>
0, *q *odd. Let *a *be any
integer in the range 1 < *a *<
*p *- 1. Then one of the
two following conditions is true.

** Proof: **Fermatâ€™s theorem
[Equation (8.2)] states that

we know that the last number in the list has
value 1. Further, each number in the list is the square of the previous number.
Therefore, one of the following possibilities must be true.

**1.
**The first number on the list, and therefore
all subsequent numbers
on the list, equals 1.

**2.
**Some number
on the list does not equal 1, but its square mod *p *does equal
1. By virtue of the first
property of prime
numbers defined above,
we know that the only number that satisfies this
condition is *p *- 1. So, in this case, the list contains an
element equal to *p *- 1.

This completes the proof.

*DETAILS OF THE *** ALGORITHM **These considerations lead
to the conclusion that, if

We can use the preceding property to devise
a test for primality. The procedure TEST takes a candidate
integer *n *as input and returns
the result **composite **if *n *is definitely not a prime,
and the result
**inconclusive **if *n *may or may not be a prime.

Let
us apply the
test to the
prime number *n *= 29. We have (*n *- 1) = 28 = 22(7) = 2*k**q*. First,
let us try
*a *= 10. We compute 107 mod 29 = 17, which is neither
1 nor 28, so we continue the test. The next calcu- lation finds that (107)2 mod 29 = 28, and the test
returns **inconclusive **(i.e., 29 may be prime).
Letâ€™s try again with *a *= 2. We have the following calculations: 27 mod 29 = 12; 214 mod 29 = 28; and the test again returns **inconclusive**. If we perform the test for all integers *a *in the range 1
through 28, we get the same **inconclusive **result, which is compatible with *n *being a prime number.

Now let us apply the test to the composite
number *n *= 13 * 17 = 221. Then (*n *-1) = 220 = 22(55) = 2*k**q*. Let us try *a *= 5. Then we have 555 mod 221 = 112, which is neither 1 nor 220 (555)2 mod 221 = 168. Because we have used all values of *j *(i.e., *j *= 0 and *j *= 1) in line 4 of the TEST algorithm, the test returns **composite**, indicating that 221 is definitely a composite num- ber. But suppose we had selected *a *= 21. Then we have 2155 mod 221 = 200; (2155)2 mod 221 = 220; and the test returns **inconclusive**, indicating that 221
may be prime. In fact, of the 218 integers
from 2 through 219, four of these will
return an inconclusive result, namely
21, 47, 174,
and 200.

*REPEATED **USE OF THE **MILLER**-RABIN *** ALGORITHM **How can we use the Miller- Rabin
algorithm to determine with a high degree of confidence whether or not an integer
is prime? It can be shown [KNUT98] that given an odd number

This gives us a basis
for determining whether
an odd integer *n *is prime
with a rea- sonable degree of
confidence. The procedure
is as follows: Repeatedly invoke TEST

(*n*) using randomly
chosen values for *a*. If, at any point, TEST returns **composite**, then *n *is determined to
be nonprime. If TEST continues to return **inconclusive**** **for *t *tests, then for a sufficiently large value of
*t*, assume that *n *is prime.

A
Deterministic Primality Algorithm

Prior to 2002, there was no known method of
efficiently proving the primality of very large numbers.
All of the algorithms in use, including
the most popular (Miller-Rabin),
produced a probabilistic result. In 2002,
Agrawal, Kayal, and Saxena [AGRA02]
developed a relatively simple deterministic algorithm
that effi- ciently determines whether a given large number is a prime. The algorithm, known as
the AKS algorithm, does not appear
to be as efficient
as the Miller-Rabin algorithm. Thus far, it has not supplanted this older, probabilistic technique [BORN03].

Distribution of Primes

It is worth
noting how many numbers are likely to be rejected
before a prime
number is found
using the Miller-Rabin test,
or any other
test for primality. A result from
num- ber theory, known as the
prime number theorem, states that the primes near *n *are
spaced on the average one every (ln *n*) integers.
Thus, on average,
one would have to
test on the order of ln(*n*) integers before a prime is found.
Because all even integers
can be immediately rejected, the
correct figure is 0.5 ln(*n*). For example, if a prime
on the order of magnitude of 2200 were sought, then about 0.5 ln(2200) = 69 trials would be
needed to find
a prime. However,
this figure is just an average.
In some places
along the number line, primes
are closely packed,
and in other places there are large gaps.

**The two consecutive
odd integers 1,000,000,000,061 and 1,000,000,000,063 are both prime. On the
other hand, 1001! ****+ ****2, 1001! ****+ ****3, ... , 1001! ****+ ****1000, 1001! ****+ ****1001 is
a sequence of 1000 consecutive composite integers.**

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Cryptography and Network Security Principles and Practice : Asymmetric Ciphers : Introduction to Number Theory : Testing for Primality |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright Â© 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.