Cryptography Reference
In-Depth Information
11.1
MILLER'S TEST
Definition
(Miller's Test.)
Let
n
be a positive integer with
n
1 = 2
s
t
where
s
is a nonnegative integer, and
t
is an
odd positive integer. We say that
n
passes Miller's test for the base
b
if either
b
t
1 (mod
n
) or
b
kt
1 (mod
n
) for some
k
= 2
j
, 0
≤
j
≤
s
1.
Let's discuss in detail how Miller's test works. Suppose you are testing the integer
n
for
primality, and obtain
b
n
1
1 (mod
n
). This doesn't tell you if
n
is prime or not, so consider
the quantity
y
= (
n
1)/2, and evaluate
x
b
y
(mod
n
). If
n
is prime we must have
x
1
(mod
n
), or
x
1 (mod
n
), since
x
2
=
x x
= (
b
(
n
1)/2
)(
b
(
n
1)/2
) =
b
(
n
1)
1 (mod
n
) by Fer-
mat's Little Theorem, and Proposition 34 says the only square roots of 1 modulo a prime
are 1 and
1. So, when we compute
x
we have the following cases to consider:
1.
x
n
x
is congruent to neither 1 nor
1 modulo
. In this case,
has a square root that is con-
n
gruent to neither 1 nor
1; hence
cannot be prime by Proposition 34 and so fails the
test.
2.
x
n
n
1 (mod
). This case says that
may be prime. We can go no further with the test
n
once we obtain a residue of
1, so we conclude that
passes the test.
3.
x
n
n
1 (mod
) This also says that
may be prime, and furthermore we can continue to
n
test
for primality in this way:
If 2|
y
, divide
y
by 2 (again) and evaluate
x
b
y
(mod
n
). Then consider as before the
three cases above.
a.
b.
If
y
is not divisible by 2, the last value for
x
was congruent to 1 modulo
n
. We can go
no further with the test, and conclude that
n
passes the test for primality.
Note that the previous procedure must eventually terminate, since
• we must eventually obtain a residue not equal to 1, or
• during each iteration we divide the value of
y
in half, and at some point
y
must fail to be
divisible by 2.
It should be clear to you that if you run a prime number through Miller's test, it will
pass.
PROPOSITION 35
If
n
is prime and
b
is a positive integer such that
n
b
, then
n
passes
Miller's test for the base
b
.
Proof.
If
n
is prime in the algorithm described above, you must eventually
1. Obtain a value for
x
1 (mod
n
), or
Search WWH ::
Custom Search