Crypto2023 Lecture10

HAI709I : Fondements cryptographiques de la sécurité, Université de Montpellier, 2023
20/11/2023. Lecture 10.
1 The Miller–Rabin primality test

For an integer number n we can verify whether it is prime by trying all potential divisors among the candi-
√
dates 1, 2, . . . , b nc. However, this procedure is very slow. If the√
binary representation of n consists of k
√
digits (i.e., 2k−1 ≤ n < 2k ), then the number of candidates n ∼ 2k = 2k/2 is exponential in k. In what
follows we discuss an efficient (poly-time) test of primality.
We know that for all prime numbers p and for all a ∈ {1, 2 . . . , p − 1}
ap−1 = 1 mod p
(Fermat’s little theorem). This observation motivates the following naive test of primality:
Fermat test of primality for an integer number n :
1. take a random number a ∈ {1, 2 . . . , n − 1}
2. compute b ← (an−1 mod n)
3. if b = 1 mod n − 1, return ”prime” ; otherwise return ”not prime”.
Fermat’s little theorem implies that for all prime numbers the Fermat test always sais prime. Is it true
that for every composite number the test say not prime with a non-negligible probability? Unfortunately,
this is not always the case. There exist composite integer numbers (cf. Carmichael numbers) for which this
test fails for all a ∈ {1, 2 . . . , n − 1}.
Fortunately, there is a test that will most likely reveal non-primality for each composite number.
Miller–Rabin test of primality for an integer number n :
1. denote n − 1 = m · 2r , where m is an odd number (the maximal odd divisor of n − 1)
2. take a random number a ∈ {1, 2 . . . , n − 1}
3. compute the series of numbers
• b0 := am mod n
• b1 := (b20 ) = am·2 mod n
• b2 := (b21 ) = am·4 mod n
..
.
r
• br := (b2r−1 ) = am·2 = an−1 mod n
(we assume that each bi belongs to {0, 1, 2, . . . , n − 1})
4. if b0 = 1, return ”prime”
1
5. if there exists an i ∈ {0, 1, . . . , r − 1} such that bi = p − 1 (equivalently, bi = −1 mod n), return
”prime”
6. in all other cases return ”not prime”
In the class we proved the following sattements:
• if n is prime, the Miller–Rabin test says ”prime” with probability 1
• if n has at least at least two different prime factors, then the Miller–Rabin test says not ”prime” with
probability ≥ 1/2.
We did not proved the fact that the probability of failure is small for n that are powers of prime numbers
(such a number is not prime but it has only one prime factor). However, the property ”n is a power of an
integer number” can be tested deterministically in polynomial time.
Theorem 1. If n is a prime number, then the Miller–Rabin test returns ”prime” with probability 1.
Sketch of the proof. First of all, from Fermat’s little theorem it follows that for every a
r
an−1 = am·2 = 1 mod n.
Thus, br = 1 mod n, and the list of the values (b0 , b1 , . . . , br ) can look like
(1, 1, 1, . . . , 1)
or
(∗, ∗ . . . , ∗, −1, 1, . . . , 1)
or
(∗, ∗ . . . , ∗, 1, 1, . . . , 1)
where ∗ denotes any number that is not equal to ±1 mod n. In the first and the second case, the test returns
the answer ”prime”. It remains to show that the third case is impossible.
The third case above means that for some i we have bi 6= ±1 mod n, and bi+1 = 1 mod n. Combin-
ing this with the fact bi+1 = b2i mod n, we see that the equation
x2 = 1 mod n
has at least three different roots: 1, −1, and bi . However, modulo a prime number n, every polynomial of
degree 2 cannot have more than 2 roots. We have arrived to a contradiction, which completes the proof.
Theorem 2. If n has at least two different prime factors, then the Miller–Rabin test returns ”not prime”
with a probability ≥ 1/2.
Sketch of the proof. If n has at least two different prime factors, than it can be represented as a product
n = n0 · n00 where n0 and n00 are co-prime integer numbers strictly greater than 1.
Let i0 denote the maximal integer number such that there exists at least one a ∈ {1, . . . , n − 1} such
that
i0
am·2 = −1 mod n.
2
(Observe that such an i0 exists: we know for sure that (p − 1)m = (−1)m mod n = −1 mod n since m
is odd.) Further, let
i0
H = {a ∈ {1, 2, . . . , n − 1} such that am·2 = ±1 mod n}
Observe that the Miller–Rabin test can return the (false) answer ”prime” for the input n only if the randomly
chosen a belongs to H. Therefore, to show that the probability of an error is ≤ 1/2, we need to prove that
|H| < (n − 1)/2.
It is not hard to see that H is a subgroup in the group (Z/nZ)× (with the operation of multiplication
modulo n). Hence, to prove that |H| < |Z/nZ|/2, it is enough to prove that H 6= Z/nZ. It remains to find
â ∈ Z/nZ such that â 6∈ H.
i i
Let us fix an a such that am·2 0 = −1 mod n. Observe that am·2 0 = −1 mod n0 . Now we inspect
the list of numbers
a, a + n0 , a + 2n0 , a + 3n0 , . . . , a + (n00 − 1)n0
We do two simple observations.
i
Fact 1. For each number b in this list we have bm·2 0 = −1 mod n0 (since all these numbers are equal to
each other modulo n0 ).
Fact 2. All these numbers are pairwise distinct modulo n00 (since the difference between every two numbers
a + in0 and a + jn0 is equal to (i − j)n0 , which is not divisible by n00 ).
From Fact 2 it follows that the list contains every possible reminder modulo n00 exactly once, so there
must be an element a + jn0 that is equal to 1 modulo n00 . We take this number as â. Buy the construction,
we have
â = −1 mod n0 and â = 1 mod n00 .
It is clear that â 6= ±1 mod n. Thus, H does not cover the whole Z/nZ, and |H| ≤ |Z/nZ|/2. This
concludes the proof.
Exercise 1. Construct a polynomial time deterministic algorithm that takes as input a binary representation
of a number n and tests whether n = mk for some integer numbers m and k > 1.
Remark 1. The Miller–Rabin test uses randomness. Can we test primality of integer numbers determin-
istically? The answer to this question is yes. The algorithm invented by Agrawal, Kayal, and Saxena is
deterministic, and it verifies primality of a given integer number in polynomial time. But in practice the
algorithm by Agrawal–Kayal–Saxena is slower than the Miller–Rabin test.
2 The RSA scheme of electronic signature

We briefly discussed an application of the asymmetric encryption (using RSA as the standard example) in a
protocol of electronic signature and the network of Certificate authorities, which certify the ownership of a
public key for Internet users.

Crypto2023 Lecture10

Uploaded by

Copyright:

Available Formats

Crypto2023 Lecture10

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Crypto2023 Lecture10

Uploaded by

Copyright:

Available Formats

HAI709I : Fondements cryptographiques de la sécurité, Université de Montpellier, 2023

20/11/2023. Lecture 10.

1 The Miller–Rabin primality test

1. take a random number a ∈ {1, 2 . . . , n − 1}

2. compute b ← (an−1 mod n)

3. if b = 1 mod n − 1, return ”prime” ; otherwise return ”not prime”.

1. denote n − 1 = m · 2r , where m is an odd number (the maximal odd divisor of n − 1)

2. take a random number a ∈ {1, 2 . . . , n − 1}

3. compute the series of numbers

(we assume that each bi belongs to {0, 1, 2, . . . , n − 1})

6. in all other cases return ”not prime”

In the class we proved the following sattements:

• if n is prime, the Miller–Rabin test says ”prime” with probability 1

2 The RSA scheme of electronic signature

You might also like