Cryptography Reference
In-Depth Information
holds but also the successive square roots obtained starting with this element follow
a very specific pattern. Thus if an integer
n
satisfies the assertion of the theorem,
then it also passes the Fermat test and one might hope that this gives a necessary and
sufficient condition for
n
to be prime. But it is easy to see that this is not the case. For
example, if
n
=
2047
=
23
·
89 and
b
=
2 then, with the same notation as above,
t
=
1023 and we have that
> Power(2, 1023) mod 2047;
1
so that the composite number 2047 satisfies the assertion of Theorem 6.6 for
b
2,
and hence 2047 is an odd composite that behaves like a prime as far as this theo-
rem is concerned. This leads to the following definition, similar to that of (Fermat)
pseudoprime above:
=
2
s
t
, with
t
odd, and
b
an integer. Then
n
is a
strong pseudoprime
to the base
b
if either
b
t
Definition 6.3
Let
n
be an odd composite number,
n
−
1
=
≡
1
(
mod
n
)
or
b
2
i
t
≡−
1
(
mod
n
)
for some
i
with 0
≤
i
≤
s
−
1.
Example 6.3
It is clear that a strong pseudoprime to the base
b
is also a
b
-pseudoprime, but strong pseudoprimes are less abundant than pseudoprimes: for
example, the Carmichael number 561 is not a strong pseudoprime to the base 2 for
we have that 560
2
4
=
·
=
=
35 in the above notation. Then, if we
compute the sequence of values
b
2
i
t
mod
n
,for0
35, i.e.,
s
4 and
t
≤
i
≤
3, we obtain:
> Power(2, 35) mod 561;
263
> Power(263, 2) mod 561;
166
> Power(166, 2) mod 561;
67
> Power(67, 2) mod 561;
1
Thus we see that 561 is not a strong pseudoprime to the base 2 (and this happens
because 67 is a square root of 1 modulo 561).
(
,
)
=
Remark 6.4
Observe that if gcd
b
n
1 and
p
is a prime that divides both
n
and
and
b
2
i
t
b
, then
b
t
1, and this
clearly implies that
n
cannot be a strong pseudoprime to the base
b
. Thus, although
not explicitly required in the definition, a necessary condition for
n
to be a strong
pseudoprime to the base
b
is that gcd
≡
0
(
mod
p
)
≡
0
(
mod
p
)
for all
i
with 0
≤
i
≤
s
−
(
b
,
n
)
=
1.
An odd integer
n
that satisfies the congruences in the definition of strong pseudo-
prime for some
b
is said to pass the
strong probable prime test
to the base
b
.This
test is given in Algorithm 6.1.
According to the previous discussion, if
n
passes the strong probable prime test,
then
n
is either prime or a strong pseudoprime to the base
b
. If, on the contrary,
n
fails
the test to base
b
, then we know from Theorem 6.6 that
n
is composite and, in this
case,
b
is said to be a
witness
(also called a
strong witness
or a
Miller-Rabin witness
)
to the compositeness of
n
, meaning that
b
serves to guarantee the compositeness of
