Cryptography Reference
In-Depth Information
F.2 Miller-Selfridge-Rabin
The Miller
F.1
-Selfridge
F.2
-Rabin
F.3
Primality Test
Let
n
−
1=2
t
m
where
m
∈
N
∈
N
. The value
n
is the input to
be tested by executing the following steps, where all modular exponentiations
are done using the repeated squaring method described on page 171.
(1) Choose a random integer
a
with 2
is odd and
t
≤
a
≤
n
−
2.
(2) Compute
a
m
(mod
n
)
.
x
≡
If
x
≡±
1 (mod
n
)
,
then terminate the algorithm with
“
n
is probably prime”.
If
t
= 1, terminate the algorithm with
“
n
is definitely composite.”
Otherwise, set
j
= 1 and go to step (3).
(3) Compute
a
2
j
m
(mod
n
)
.
x
≡
≡
If
x
1 (mod
n
), then terminate the algorithm with
“
n
is definitely composite.”
If
x
≡−
1 (mod
n
), terminate the algorithm with
“
n
is probably prime.”
Otherwise set
j
=
j
+ 1 and go to step (4).
F.1
Gary Miller obtained his Ph.D. in computer science from U.C. Berkeley in 1974. He is
currently a professor in computer science at Carnegie-Mellon University. His expertise lies in
computer algorithms.
F.2
This test is most often called the
Miller-Rabin Test
in the literature. However, John
Selfridge was using the test in 1974 before Miller first published the result, so we credit
Selfridgeherewiththisrecognition. JohnSelfridgewasborninKetchican,Alaska,onFebruary
17, 1927. He received his doctorate from U.C.L.A. in August of 1958, and became a professor
at Pennsylvania State University six years later. He is a pioneer in computational number
theory.
F.3
Michael Rabin (1931-) was born in Breslau, Germany (now Wroclaw, Poland), in 1931.
In 1956, he obtained his Ph.D. from Princeton University where he later taught. In 1958, he
movedtotheHebrewUniversityinJerusalem. Heisknownforhisseminalworkinestablishing
arigorousmathematicalfoundationforfiniteautomatatheory. Forsuchachievements, hewas
co-recipient of the 1976 Turing award, along with Dana S. Scott. He now divides his time
between positions at Harvard and the Hebrew University in Jerusalem.
Search WWH ::
Custom Search