Cryptography Reference
In-Depth Information
≡
91
≡
13
to the bases
9
and
10
, for which we have
9
45
n
=91=7
·
1mod91
≡
1
91
≡−
1mod91
.
9
An Euler pseudoprime to a base
a
is always a pseudoprime to the base
a
(see page 221), since by squaring
a
(
n
−
1)
/
2
and
10
45
≡
n
mod
n
it follows that
a
n
−
1
1mod
n
.
There is, however, no counterpart to the Carmichael numbers for the Euler
criterion, and based on the following observations of R. Solovay and V. Strassen
we can see that the risk of a false test result for Euler pseudoprimes is favorably
bounded from above.
≡
(i)
For a composite number
n
the number of integers
a
relatively prime to
n
for
which
a
(
n
−
1)
/
2
≡
n
mod
n
is at most
1
2
φ
(
n
)
(see [Kobl], Section 2.2,
Exercise 21). From this we have the following proposition.
(ii)
The probability that for a composite number
n
and
k
randomly selected
numbers
a
1
,...,a
k
relatively prime to
n
one has
a
(
n
−
1)
/
2
≡
a
n
mod
n
,
r
for
1
≤ r ≤ k
,isatmost
2
−
k
.
These results make it possible to implement the Euler criterion as a
probabilistic primality test, where “probabilistic” means that if the test returns
that result “
n
is not prime,” then this result is definitive, but it is only with a
certain probability of error that we may infer that
n
is in fact prime.
Algorithm: Probabilistic primality test à la Solvay-Strassen for testing a natural
number
n
for compositeness
1.
Choose a random number
a ≤ n −
1
with
gcd(
a, n
)=1
.
2.
If has
a
(
n
−
1)
/
2
≡
n
mod
n
, then output “
n
is a probable prime.”
Otherwise, output “
n
is composite.”
This test requires computation time
O
log
3
n
for the calculation of the
exponent and the Jacobi symbol. By repeated application of this test we can
reduce the probability of error in step (ii). For example, for
k
=60
we obtain a
vanishingly small probability of error less than
2
−
60
10
−
18
, and D. Knuth has
indicated that this value is less than that of a transient hardware error, caused, for
example, by an alpha particle that has found its way into the CPU or memory of a
computer and thereby switched the value of a bit.
We might be satisfied with this test, since we have control over the probability
of error and we have efficient algorithms for all the required computations.
However, there are results that lead to a more efficient algorithm. For this we
≈
We have
9
3
≡
10
6
9
≡
1mod91
, since 3 is the order of 9 and 6 is the order of 10 in
Z
91
.
Therefore,
9
45
≡
9
3
·
15
≡
1mod91
and
10
45
≡
10
6
·
7+3
≡
10
3
≡−
1mod91
.
