Get best of the week

Fermat and Miller-Rabin simplicity tests

Salute to the Habrovsk citizens! Today we continue to share useful material, a translation of which was prepared specifically for students of the course "Algorithms for Developers" .



Given a number n, how to understand that this number is prime? Suppose that it is ninitially odd, because otherwise the task is quite simple.

The most obvious idea would be to look for all the divisors of a number n, but so far the main problem is to find an efficient algorithm.

Farm Test


By Fermat’s Theorem , if nis a prime, then the following equality holds for any a . From here we can derive the Fermat test rule for checking the simplicity of a number: take a random one and check whether the equality holds . If equality is not respected, then most likely - composite. Nevertheless, the condition of equality can be met, even if it is not a simple one. Take for example . According to the Chinese remainder theorem : where each the Z ∈ a * 561 corresponds to the following: According to Fermat's Last Theorem, , , . Since 2, 10, and 16 are all 560 dividers, this means thatan−1=1 (mod n)a ∈ {1, ..., n−1} an−1=1 (mod n)n

nn = 561 = 3 × 11 × 17

Z561 = Z3 × Z11 × Z17



(x,y,z) ∈ Z∗3×Z∗1111×Z∗17.

x2=1y10=1 z16=1(x,y,z)560 = (1, 1, 1)in other words for anyone . It does not matter which a we choose, 561 will always pass the Fermat test, despite the fact that it is composite, as long as a is mutually simple with . Such numbers are called Carmichael numbers and it turns out that there are an infinite number of them. If it is not coprime with , then it does not pass the Fermat test, but in this case we can abandon the tests and continue to search for divisors by computing the GCD ( a, n ).a560 = 1 a ∈ Z∗561

n

ann

Miller-Rabin Test


We can refine the test by saying that n is simple if and only if the solutions are . Thus, if n passes the Fermat test, that is , then we check to ensure that , since this is the square root of 1. Unfortunately, numbers such as 1729, the third Carmichael number, can still fool this improved test. What if we iterate over? That is, until this is possible, we will reduce the exponent by half, until we reach a number other than 1. If we get in the end something other than -1, then it will be composite. Speaking more formally, then let 2 Sx2 = 1 (mod n) x = ±1

an−1 = 1a(n−1)/2 = ±1a(n−1)/2

n

will be the largest power of 2, divisible by n-1, that is, for some odd number . Each number in the sequence , , ..., . This is the square root of the previous member of the sequence. Then if is a prime number, then the sequence must begin with 1 and each subsequent number must also be 1, or the first member of the sequence may not be 1, but then it is -1. The Miller-Rabin test takes random . If the above sequence does not start with 1, or the first member of the sequence is not 1 or -1, then it is not simple. It turns out that for any compoundn−1=2Sqq

an−1 = a(2^S)qa(2^S-1)qaq



n

a∈ Znn

n, including Carmichael numbers, the probability of passing the Miller-Rabin test is approximately 1/4. (On average, much less.) Thus, the likelihood that nseveral test runs will pass decreases exponentially.

If the nMiller-Rabin test fails with a sequence starting with 1, then we get a non-trivial square root of 1 modulo n, and we can effectively find the divisors n . Therefore, Carmichael numbers are always convenient to factor.

When the test is applied to numbers of the form pq, where pand qare large prime numbers, they do not pass the Miller-Rabin test in almost all cases, since the sequence does not start with 1. So, we won’t be able to break the RSA.

In practice, the Miller-Rabin test is implemented as follows:

  1. Given n, you need to find ssuch that for some odd .n – 1 = 2Sqq
  2. Take random a ∈ {1,...,n−1}
  3. If a q = 1, then nthe test passes and we stop execution.
  4. To i= 0, ... , s−1check equality . If equality is satisfied, then the test passes (stop execution).a(2^i)q = −1n
  5. If none of the above conditions is met, then n- composite.

Before performing the Miller-Rabin test, it is worthwhile to carry out a few more trivial divisions into small primes.

Strictly speaking, these tests are tests for whether a number is considered to be compound, since they do not prove in fact that the number being checked is prime, but they definitely prove that it can be compound.

There are still deterministic algorithms working in polynomial time to determine simplicity (Agrawal, Kayal and Saxena ), but today they are considered impractical.

Source: https://habr.com/ru/post/undefined/

More articles:


All Articles