Cryptography Reference
In-Depth Information
Finally, Carmichael numbers exist (we have seen
n
561 as an example). We further
know that there exist an infinite number of such numbers.
2
=
7.1.3
Solovay-Strassen Test
Prime numbers have other properties which can be used by primality tests. For instance,
the Euler test says that for primes
p
and 0
<
b
<
p
,wehave
b
p
b
p
−
1
≡
(mod
p
)
2
where
p
is the Legendre symbol. The following theorem tells us that this necessary
property is also sufficient (when considering the Jacobi symbol). The Solovay-Strassen
primality test is based on it.
Theorem 7.4.
Let n
be
an odd number. n is prime if and only if for any b such that
0
≡
n
(mod
n
)
.
We recall that
n
is the Jacobi symbol which is defined as follows. Let
n
n we have b
n
−
1
<
b
<
2
p
α
1
1
=
···
p
α
r
r
be the factorization on
n
into pairwise different odd prime numbers
p
1
,...,
p
r
.We
define
b
n
b
p
1
α
1
b
p
r
α
r
=
···
where
p
i
is the
Legendre symbol
defined by
⎧
⎨
b
p
i
0 f
b
mod
p
i
=
0
1 f
b
is a quadratic residue in
Z
p
i
=
⎩
1 f
b
is not a quadratic residue in
Z
p
i
.
−
It is important to emphasize that the Jacobi symbol can be efficiently computed. This
can be done using an algorithm which is very similar to the Euclid algorithm. We
actually use the following properties:
1.
b
=
a
mod
b
for
b
odd,
2.
a
c
=
c
c
for
c
odd,
3.
a
=
1 (mod 8) and
a
=−
1if
a
≡±
1if
a
≡±
3 (mod 8) for
a
odd,
4.
b
=−
a
if
a
3 (mod 4) and
b
=
a
otherwise for
a
and
b
odd.
≡
b
≡
As an example, we can compute both term
s o
f the test for
b
=
362 and
n
=
561
(a Carmichael number). First we compute
b
n
−
1
362
280
mod
n
=
mod 561. We have
2
2
For more information we recommend Ref. [53].
Search WWH ::
Custom Search