Тест миллера рабина вероятность ошибки

The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen primality test.

It is of historical significance in the search for a polynomial-time deterministic primality test. Its probabilistic variant remains widely used in practice, as one of the simplest and fastest tests known.

Gary L. Miller discovered the test in 1976; Miller’s version of the test is deterministic, but its correctness relies on the unproven extended Riemann hypothesis.^[1] Michael O. Rabin modified it to obtain an unconditional probabilistic algorithm in 1980.^[2][a]

Mathematical concepts[edit]

Similarly to the Fermat and Solovay–Strassen tests, the Miller–Rabin primality test checks whether a specific property, which is known to hold for prime values, holds for the number under testing.

Strong probable primes[edit]

The property is the following. For a given odd integer n > 2, let’s write n − 1 as 2^sd where s is a positive integer and d is an odd positive integer. Let’s consider an integer a, called a base, which is coprime to n.
Then, n is said to be a strong probable prime to base a if one of these congruence relations holds:

The idea beneath this test is that when n is an odd prime, it passes the test because of two facts:

• by Fermat’s little theorem, (this property alone defines the weaker notion of probable prime to base a, on which the Fermat test is based);
• the only square roots of 1 modulo n are 1 and −1.

Hence, by contraposition, if n is not a strong probable prime to base a, then n is definitely composite, and a is called a witness for the compositeness of n.

However, this property is not an exact characterization of prime numbers. If n is composite, it may nonetheless be a strong probable prime to base a, in which case it is called a strong pseudoprime, and a is a strong liar.

Choices of bases[edit]

Thankfully, no composite number is a strong pseudoprime to all bases at the same time (contrary to the Fermat primality test for which Fermat pseudoprimes to all bases exist: the Carmichael numbers). However no simple way of finding a witness is known. A naïve solution is to try all possible bases, which yields an inefficient deterministic algorithm. The Miller test is a more efficient variant of this (see section Miller test below).

Another solution is to pick a base at random. This yields a fast probabilistic test. When n is composite, most bases are witnesses, so the test will detect n as composite with a reasonably high probability (see section Accuracy below). We can quickly reduce the probability of a false positive to an arbitrarily small rate, by combining the outcome of as many independently chosen bases as necessary to achieve the said rate. This is the Miller–Rabin test. The number of bases to try does not depend on n. There seems to be diminishing returns in trying many bases, because if n is a pseudoprime to some base, then it seems more likely to be a pseudoprime to another base.^[4]: §8

Note that a^d ≡ 1 (mod n) holds trivially for a ≡ 1 (mod n), because the congruence relation is compatible with exponentiation. And a^d = a^20d ≡ −1 (mod n) holds trivially for a ≡ −1 (mod n) since d is odd, for the same reason. That is why random a are usually chosen in the interval 1 < a < n − 1.

For testing arbitrarily large n, choosing bases at random is essential, as we don’t know the distribution of witnesses and strong liars among the numbers 2, 3, …, n − 2.^[b]

However, a pre-selected set of a few small bases guarantees the identification of all composites up to a pre-computed maximum. This maximum is generally quite large compared to the bases. This gives very fast deterministic tests for small enough n (see section Testing against small sets of bases below).

Proofs[edit]

Here is a proof that, if n is a prime, then the only square roots of 1 modulo n are 1 and −1.

Here is a proof that, if n is an odd prime, then it is a strong probable prime to base a.

Example[edit]

Suppose we wish to determine if n = 221 is prime. We write n − 1 as 2² × 55, so that we have s = 2 and d = 55. We randomly select a number a such that 2 ≤ a ≤ n−2, say a = 174. We proceed to compute:

• a^20d mod n = 174⁵⁵ mod 221 = 47 ≠ 1, n − 1
• a^21d mod n = 174¹¹⁰ mod 221 = 220 = n − 1.

Since 220 ≡ −1 mod n, either 221 is prime, or 174 is a strong liar for 221. We try another random a, this time choosing a = 137:

• a^20d mod n = 137⁵⁵ mod 221 = 188 ≠ 1, n − 1
• a^21d mod n = 137¹¹⁰ mod 221 = 205 ≠ n − 1.

Hence 137 is a witness for the compositeness of 221, and 174 was in fact a strong liar. Note that this tells us nothing about the factors of 221 (which are 13 and 17). However, the example with 341 in a later section shows how these calculations can sometimes produce a factor of n.

Miller–Rabin test[edit]

The algorithm can be written in pseudocode as follows. The parameter k determines the accuracy of the test. The greater the number of rounds, the more accurate the result.^[6]

Input #1: n > 2, an odd integer to be tested for primality
Input #2: k, the number of rounds of testing to perform
Output: “composite” if n is found to be composite, “probably prime” otherwise

let s > 0 and d odd > 0 such that n − 1 = 2sd  # by factoring out powers of 2 from n − 1
repeat k times:
    a ← random(2, n − 2)  # n is always a probable prime to base 1 and n − 1
    x ← ad mod n
    repeat s times:
        y ← x2 mod n
        if y = 1 and x ≠ 1 and x ≠ n − 1 then # nontrivial square root of 1 modulo n
            return “composite”
        x ← y
    if y ≠ 1 then
        return “composite”
return “probably prime”

Complexity[edit]

Using repeated squaring, the running time of this algorithm is O(k log³ n), where n is the number tested for primality, and k is the number of rounds performed; thus this is an efficient, polynomial-time algorithm. FFT-based multiplication (Harvey-Hoeven algorithm) can decrease the running time to O(k log² n log log n) = Õ(k log² n).

Accuracy[edit]

The error made by the primality test is measured by the probability that a composite number is declared probably prime. The more bases a are tried, the better the accuracy of the test. It can be shown that if n is composite, then at most 1/4 of the bases a are strong liars for n.^[2][7] As a consequence, if n is composite then running k iterations of the Miller–Rabin test will declare n probably prime with a probability at most 4^−k.

This is an improvement over the Solovay–Strassen test, whose worst‐case error bound is 2^−k. Moreover, the Miller–Rabin test is strictly stronger than the Solovay–Strassen test in the sense that for every composite n, the set of strong liars for n is a subset of the set of Euler liars for n, and for many n, the subset is proper.

In addition, for large values of n, the probability for a composite number to be declared probably prime is often significantly smaller than 4^−k. For instance, for most numbers n, this probability is bounded by 8^−k; the proportion of numbers n which invalidate this upper bound vanishes as we consider larger values of n.^[8] Hence the average case has a much better accuracy than 4^−k, a fact which can be exploited for generating probable primes (see below). However, such improved error bounds should not be relied upon to verify primes whose probability distribution is not controlled, since a cryptographic adversary might send a carefully chosen pseudoprime in order to defeat the primality test.^[c]
In such contexts, only the worst‐case error bound of 4^−k can be relied upon.

The above error measure is the probability for a composite number to be declared as a strong probable prime after k rounds of testing; in mathematical words, it is the conditional probability

where P is the event that the number being tested is prime, and MR_k is the event that it passes the Miller–Rabin test with k rounds. We are often interested instead in the inverse conditional probability : the probability that a number which has been declared as a strong probable prime is in fact composite. These two probabilities are related by Bayes’ law:

In the last equation, we simplified the expression using the fact that all prime numbers are correctly reported as strong probable primes (the test has no false negative). By dropping the left part of the denominator, we derive a simple upper bound:

Hence this conditional probability is related not only to the error measure discussed above — which is bounded by 4^−k — but also to the probability distribution of the input number. In the general case, as said earlier, this distribution is controlled by a cryptographic adversary, thus unknown, so we cannot deduce much about . However, in the case when we use the Miller–Rabin test to generate primes (see below), the distribution is chosen by the generator itself, so we can exploit this result.

Deterministic variants[edit]

Miller test[edit]

The Miller–Rabin algorithm can be made deterministic by trying all possible a below a certain limit. Taking n as the limit would imply O(n) trials, hence the running time would be exponential with respect to the size log n of the input. To improve the running time, the challenge is then to lower the limit as much as possible while keeping the test reliable.

If the tested number n is composite, the strong liars a coprime to n are contained in a proper subgroup of the group (Z/nZ)*, which means that if we test all a from a set which generates (Z/nZ)*, one of them must lie outside the said subgroup, hence must be a witness for the compositeness of n. Assuming the truth of the generalized Riemann hypothesis (GRH), it is known that the group is generated by its elements smaller than O((ln n)²), which was already noted by Miller.^[1] The constant involved in the Big O notation was reduced to 2 by Eric Bach.^[10] This leads to the following deterministic primality testing algorithm, known as the Miller test:

Input: n > 2, an odd integer to be tested for primality
Output: “composite” if n is composite, “prime” otherwise

let s > 0 and d odd > 0 such that n − 1 = 2sd  # by factoring out powers of 2 from n − 1
for all a in the range [2, min(n − 2, ⌊2(ln n)2⌋)]:
    x ← ad mod n
    repeat s times:
        y ← x2 mod n
        if y = 1 and x ≠ 1 and x ≠ n − 1 then  # nontrivial square root of 1 modulo n
            return “composite”
        x ← y
    if y ≠ 1 then
        return “composite”
return “prime”

The full power of the generalized Riemann hypothesis is not needed to ensure the correctness of the test: as we deal with subgroups of even index, it suffices to assume the validity of GRH for quadratic Dirichlet characters.^[7]

The running time of the algorithm is, in the soft-O notation, Õ((log n)⁴) (using FFT‐based multiplication).

The Miller test is not used in practice. For most purposes, proper use of the probabilistic Miller–Rabin test or the Baillie–PSW primality test gives sufficient confidence while running much faster. It is also slower in practice than commonly used proof methods such as APR-CL and ECPP which give results that do not rely on unproven assumptions. For theoretical purposes requiring a deterministic polynomial time algorithm, it was superseded by the AKS primality test, which also does not rely on unproven assumptions.

Testing against small sets of bases[edit]

When the number n to be tested is small, trying all a < 2(ln n)² is not necessary, as much smaller sets of potential witnesses are known to suffice. For example, Pomerance, Selfridge, Wagstaff^[4] and Jaeschke^[11] have verified that

• if n < 2,047, it is enough to test a = 2;
• if n < 1,373,653, it is enough to test a = 2 and 3;
• if n < 9,080,191, it is enough to test a = 31 and 73;
• if n < 25,326,001, it is enough to test a = 2, 3, and 5;
• if n < 3,215,031,751, it is enough to test a = 2, 3, 5, and 7;
• if n < 4,759,123,141, it is enough to test a = 2, 7, and 61;
• if n < 1,122,004,669,633, it is enough to test a = 2, 13, 23, and 1662803;
• if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11;
• if n < 3,474,749,660,383, it is enough to test a = 2, 3, 5, 7, 11, and 13;
• if n < 341,550,071,728,321, it is enough to test a = 2, 3, 5, 7, 11, 13, and 17.

Using the work of Feitsma and Galway enumerating all base 2 pseudoprimes in 2010, this was extended (see OEIS: A014233), with the first result later shown using different methods in Jiang and Deng:^[12]

• if n < 3,825,123,056,546,413,051, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, and 23.
• if n < 18,446,744,073,709,551,616 = 2⁶⁴, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37.

Sorenson and Webster^[13] verify the above and calculate precise results for these larger than 64‐bit results:

• if n < 318,665,857,834,031,151,167,461, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37.
• if n < 3,317,044,064,679,887,385,961,981, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, and 41.

Other criteria of this sort, often more efficient (fewer bases required) than those shown above, exist.^{[14][15][16][17]} They give very fast deterministic primality tests for numbers in the appropriate range, without any assumptions.

There is a small list of potential witnesses for every possible input size (at most b values for b‐bit numbers). However, no finite set of bases is sufficient for all composite numbers. Alford, Granville, and Pomerance have shown that there exist infinitely many composite numbers n whose smallest compositeness witness is at least (ln n)^{1/(3ln ln ln n)}.^[18] They also argue heuristically that the smallest number w such that every composite number below n has a compositeness witness less than w should be of order Θ(log n log log n).

Variants for finding factors[edit]

By inserting greatest common divisor calculations into the above algorithm, we can sometimes obtain a factor of n instead of merely determining that n is composite. This occurs for example when n is a probable prime to base a but not a strong probable prime to base a.^[19]: 1402

If x is a nontrivial square root of 1 modulo n,

• since x² ≡ 1 (mod n), we know that n divides x² − 1 = (x − 1)(x + 1);
• since x ≢ ±1 (mod n), we know that n does not divide x − 1 nor x + 1.

From this we deduce that A = gcd(x − 1, n) and B = gcd(x + 1, n) are nontrivial (not necessarily prime) factors of n (in fact, since n is odd, these factors are coprime and n = AB). Hence, if factoring is a goal, these gcd calculations can be inserted into the algorithm at little additional computational cost. This leads to the following pseudocode, where the added or changed code is highlighted:

Input #1: n > 2, an odd integer to be tested for primality
Input #2: k, the number of rounds of testing to perform
Output: (“multiple of”, m) if a nontrivial factor m of n is found,
        “composite” if n is otherwise found to be composite,
        “probably prime” otherwise

let s > 0 and d odd > 0 such that n − 1 = 2sd  # by factoring out powers of 2 from n − 1
repeat k times:
    a ← random(2, n − 2)  # n is always a probable prime to base 1 and n − 1
    x ← ad mod n
    repeat s times:
        y ← x2 mod n
        if y = 1 and x ≠ 1 and x ≠ n − 1 then  # nontrivial square root of 1 modulo n
            return (“multiple of”, gcd(x − 1, n))
        x ← y
    if y ≠ 1 then
        return “composite”
return “probably prime”

This is not a probabilistic factorization algorithm because it is only able to find factors for numbers n which are pseudoprime to base a (in other words, for numbers n such that aⁿ⁻¹ ≡ 1 mod n). For other numbers, the algorithm only returns “composite” with no further information.

For example, consider n = 341 and a = 2. We have n − 1 = 85 × 4. Then 2⁸⁵ mod 341 = 32 and 32² mod 341 = 1. This tells us that n is a pseudoprime base 2, but not a strong pseudoprime base 2. By computing a gcd at this stage, we find a factor of 341: gcd(32 − 1, 341) = 31. Indeed, 341 = 11 × 31.

In order to find factors more often, the same ideas can also be applied to the square roots of −1 (or any other number).
This strategy can be implemented by exploiting knowledge from previous rounds of the Miller–Rabin test. In those rounds we may have identified a square root modulo n of −1, say R. Then, when x² mod n = n − 1, we can compare the value of x against R: if x is neither R nor n−R, then gcd(x − R, n) and gcd(x + R, n) are nontrivial factors of n.^[14]

Generation of probable primes[edit]

The Miller–Rabin test can be used to generate strong probable primes, simply by drawing integers at random until one passes the test. This algorithm terminates almost surely (since at each iteration there is a chance to draw a prime number). The pseudocode for generating b‐bit strong probable primes (with the most significant bit set) is as follows:

Input #1: b, the number of bits of the result
Input #2: k, the number of rounds of testing to perform
Output: a strong probable prime n

while True:
    pick a random odd integer n in the range [2b−1, 2b−1]
    if the Miller–Rabin test with inputs n and k returns “probably prime” then
        return n

Complexity[edit]

Of course the worst-case running time is infinite, since the outer loop may never terminate, but that happens with probability zero. As per the geometric distribution, the expected number of draws is (reusing notations from earlier).

As any prime number passes the test, the probability of being prime gives a coarse lower bound to the probability of passing the test. If we draw odd integers uniformly in the range [2^b−1, 2^b−1], then we get:

where π is the prime-counting function. Using an asymptotic expansion of π (an extension of the prime number theorem), we can approximate this probability when b grows towards infinity. We find:

Hence we can expect the generator to run no more Miller–Rabin tests than a number proportional to b. Taking into account the worst-case complexity of each Miller–Rabin test (see earlier), the expected running time of the generator with inputs b and k is then bounded by O(k b⁴) (or Õ(k b³) using FFT-based multiplication).

Accuracy[edit]

The error measure of this generator is the probability that it outputs a composite number.

Using the relation between conditional probabilities (shown in an earlier section) and the asymptotic behavior of (shown just before), this error measure can be given a coarse upper bound:

Hence, for large enough b, this error measure is less than . However, much better bounds exist.

Using the fact that the Miller–Rabin test itself often has an error bound much smaller than 4^−k (see earlier), Damgård, Landrock and Pomerance derived several error bounds for the generator, with various classes of parameters b and k.^[8] These error bounds allow an implementor to choose a reasonable k for a desired accuracy.

One of these error bounds is 4^−k, which holds for all b ≥ 2 (the authors only showed it for b ≥ 51, while Ronald Burthe Jr. completed the proof with the remaining values 2 ≤ b ≤ 50^[20]). Again this simple bound can be improved for large values of b. For instance, another bound derived by the same authors is:

which holds for all b ≥ 21 and k ≥ b/4. This bound is smaller than 4^−k as soon as b ≥ 32.

Notes[edit]

References[edit]

External links[edit]

• Weisstein, Eric W. «Rabin-Miller Strong Pseudoprime Test». MathWorld.
• Interactive Online Implementation of the Deterministic Variant (stepping through the algorithm step-by-step)
• Applet (German)
• Miller–Rabin primality test in C#
• Miller–Rabin primality test in JavaScript using arbitrary precision arithmetic

Тесты Ферма и Миллера-Рабина на простоту

Салют хабровчане! Сегодня мы продолжаем делиться полезным материалом, перевод которого подготовлен специально для студентов курса «Алгоритмы для разработчиков».

Дано некоторое число n, как понять, что это число простое? Предположим, что n изначально нечетное, поскольку в противном случае задача совсем простая.

Самой очевидной идеей было бы искать все делители числа n, однако до сих пор основная проблема заключается в том, чтобы найти эффективный алгоритм.

Тест Ферма

По Теореме Ферма, если n – простое число, тогда для любого a справедливо следующее равенство an−1=1 (mod n). Отсюда мы можем вывести правило теста Ферма на проверку простоты числа: возьмем случайное a ∈ {1, ..., n−1} и проверим будет ли соблюдаться равенство an−1=1 (mod n). Если равенство не соблюдается, значит скорее всего n – составное.

Тем не менее, условие равенства может быть соблюдено, даже если n – не простое. Например, возьмем n = 561 = 3 × 11 × 17. Согласно Китайской теореме об остатках:

Z561 = Z3 × Z11 × Z17

, где каждое a ∈ Z^∗₅₆₁ отвечает следующему:

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

По теореме Ферма, x2=1, y10=1, и z16=1. Поскольку 2, 10 и 16 все являются делителями 560, это значит, что (x,y,z)560 = (1, 1, 1), другими словами a560 = 1 для любого a ∈ Z∗561.

Не имеет значения какое a мы выберем, 561 всегда будет проходить тест Ферма несмотря на то, что оно составное, до тех пор, пока a является взаимно простым с n. Такие числа называются числами Кармайкла и оказывается, что их существует бесконечное множество.

Если a не взаимно простое с n, то оно тест Ферма не проходит, но в этом случае мы можем отказаться от тестов и продолжить искать делители n, вычисляя НОД(a,n).

Тест Миллера-Рабина

Мы можем усовершенствовать тест, сказав, что n — простое тогда и только тогда, когда решениями x2 = 1 (mod n) являются x = ±1.

Таким образом, если n проходит тест Ферма, то есть an−1 = 1, тогда мы проверяем еще чтобы a(n−1)/2 = ±1, поскольку a(n−1)/2 это квадратный корень 1.

К сожалению, такие числа, как, например 1729 — третье число Кармайкла до сих пор могут обмануть этот улучшенный тест. Что если мы будем проводить итерации? То есть пока это будет возможно, мы будем уменьшать экспоненту вдвое, до тех пор, пока не дойдем до какого-либо числа, помимо 1. Если мы получим в итоге что-то, кроме -1, тогда n будет составным.

Если говорить более формально, то пускай 2^S будет самой большой степенью 2, делящейся на n-1, то есть n−1=2Sq для какого-то нечетного числа q. Каждое число из последовательности

an−1 = a(2^S)q, a(2^S-1)q,…, aq.

Это квадратный корень предшествующего члена последовательности.

Тогда если n – простое число, то последовательность должна начинаться с 1 и каждое последующее число тоже должно быть 1, или же первый член последовательность может быть не равен 1, но тогда он равен -1.

Тест Миллера-Рабина берет случайное a∈ Zn. Если вышеуказанная последовательность не начинается с 1, либо же первый член последовательности не равен 1 или -1, тогда n – не простое.

Оказывается, что для любого составного n, включая числа Кармайкла, вероятность пройти тест Миллера-Рабина равна примерно 1/4. (В среднем значительно меньше.) Таким образом, вероятность того, что n пройдет несколько прогонов теста, уменьшается экспоненциально.

Если n не проходит тест Миллера-Рабина с последовательностью начинающейся с 1, тогда у нас появляется нетривиальный квадратный корень из 1 по модулю n, и мы можем эффективно находить делители n. Поэтому числа Кармайкла всегда удобно раскладывать на множители.

Когда тест применяется к числам вида pq, где p и q – большие простые числа, они не проходят тест Миллера-Рабина практически во всех случаях, поскольку последовательность не начинается с 1. Итого, так мы RSA сломать не сможем.

На практике тест Миллера-Рабина реализуется следующим образом:

1. Дано n, нужно найти s, такое что n – 1 = 2Sq для некоторого нечетного q.
2. Возьмем случайное a ∈ {1,...,n−1}
3. Если a^q = 1, то n проходит тест и мы прекращаем выполнение.
4. Для i= 0, ... , s−1 проверить равенство a(2^i)q = −1. Если равенство выполняется, то n проходит тест (прекращаем выполнение).
5. Если ни одно из вышеприведенных условий не выполнено, то n – составное.

Перед выполнением теста Миллера-Рабина стоит провести еще несколько тривиальных делений на маленькие простые числа.

Строго говоря эти тесты являются тестами на то считается ли число составным, поскольку они не доказывают по сути, что проверяемое число простое, но точно доказывают, что оно может оказаться составным.

Существуют еще детерминированные алгоритма работающие за полиномиальное время для определения простоты (Agrawal, Kayal и Saxena), однако на сегодняшний день они считаются непрактичными.

Калькулятор выполняет тест простоты Миллера-Рабина и выясняет может ли заданное число быть простым или нет. Если ответ отрицательный — число составное, если ответ положительный, то число с большой вероятностью простое. Тест использует заданное число оснований (пробных свидетелей простоты), которые вводятся списком или генерируются случайным образом в диапазоне от 2 до n-1, где n — проверяемое число. Калькулятор может выдавать пошаговую детализацию работы теста. Информацию по алгоритму Миллера-Рабина можно найти сразу за калькулятором.

Алгоритм теста простоты Миллера-Рабина

Для проверки на простоту числа алгоритмом Миллера-Рабина мы должны привести четное число n-1 число к виду 2^sd, где n-тестируемое число, d — нечетное число, s — степень двойки. Числа s и d можно получить последовательным делением n-1 на 2.
Тогда мы проверяем, что для любого целого a, в диапазоне [2..n-1], справедливо хотя бы одно из условий:

В условии 2. r берется в диапазоне [0..s).

Если хотя бы одно условие выполняется — значит выбранное a — является свидетелем простоты числа n, и число n с большой вероятностью может быть простым. Для увеличения этой вероятности мы повторяем тест для другого случайно выбранного основания.
Если оба условия не выполняются, то число n — составное и дальнейшее тестирование можно прекратить.
Тест Миллера-Рабина успешно справляется с числами Кармайкла, которые не поддаются тесту Ферма. К примеру число 29341, ошибочно определяемое тестом Ферма, как возможно простое, определяется как составное тестом Миллера-Рабина, уже по основанию 3.
В отличие от теста Ферма, для теста Миллера-Рабина нет плохих тестируемых чисел. Для любого числа тест дает правильный ответ с большой вероятностью. Неверный результат работы определяется лишь случайным выбором пробных свидетелей, вероятность чего мала ¹.
Согласно исследованию Рабина не более четверти чисел в диапазоне [1..n) не являются свидетелями² (т.е. дают ошибочный результат в тесте Миллера-Рабина), поэтому, получая потенциальных свидетелей случайным образом k раз, вероятность ошибки теста будет не более 1/4^k.

ФЕДЕРАЛЬНОЕ
АГЕНТСТВО СВЯЗИ

ФЕДЕРАЛЬНОЕ
ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ
ВЫСШЕГО ОБРАЗОВАНИЯ

«САНКТ-ПЕТЕРБУРГСКИЙ
ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М.А.
БОНЧ-БРУЕВИЧА»

(СПбГУТ)

Факультет
Инфокоммуникационных
сетей и систем

Кафедра
Защищенных
систем связи

ОТЧЕТ
ПО ЛАБОРТОРНОЙ РАБОТЕ №9

Проверка
заданного числа

(тема
отчета)

Направление/специальность
подготовки

10.03.01
Информационная безопасность

(код
и наименование направления/специальности)

Студенты:

(Ф.И.О.,
№ группы) (подпись)

Преподаватель:

Кушнир
Д.В.

(уч.
степень, уч. звание, Ф.И.О.) (подпись)

Оглавление

Теория…………………………………………………………………………….3

Ход
работы……………………………………………………………………….5

Теория

Тест Рабина-Миллера

Тест Миллера — Рабина —
вероятностный полиномиальный тест
простоты. Тест Миллера — Рабина позволяет
эффективно определять, является ли
данное число составным. Однако, с его
помощью нельзя строго доказать простоту
числа. Тем не менее тест Миллера — Рабина
часто используется в криптографии для
получения больших случайных простых
чисел.

Алгоритм был разработан Гари
Миллером в 1976 году и модифицирован
Майклом Рабином в 1980 году.

Как и для теста Ферма, все
числа m>1,
которые не проходят этот тест – составные,
а числа, которые проходят, могут быть
простыми. Для этого теста нет аналогов
чисел Кармайкла. В 1980 году было доказано,
что вероятность ошибки теста Рабина-Миллера
не превышает 1/4. Таким образом, применяя
тест Рабина-Миллера r
раз для разных
оснований, мы получаем вероятность
ошибки 2^−2r.

Число m — 1 однозначно представляется в виде m — 1=2^s∙t,
где t
нечётно.
Целое число a,
1< a < m,
называется свидетелем
простоты числа
m,
если выполняются два условия:

1. m
   не
   делится на a;

2. a^t ≡ 1
   mod m
   или существует целое k,
   0≤ k < s,
   такое, что:
   

Теорема Рабина утверждает, что составное нечётное число m имеет не более 

φ(m)/4
различных свидетелей простоты, где φ(m)
–
функция Эйлера.

Алгоритм теста Рабина-Миллера

Алгоритм
параметризуется
количеством
раундов
r.
Рекомендуется
брать
r

порядка
величины log₂(m),
где
m
—
проверяемое
число.

Для
данного
m
находят
такое
целое
число
s
и
целое
нечётное
число
t,

что
m
−
1
= 2^s∙t.
Выбирается
случайное
число
a,1
< a
< m.
Если
a
не
является
свидетелем
простоты
числа
m,
то
выдается
ответ
«m
— составное»,
и
алгоритм
завершается.
Иначе,
выбирается
новое
случайное
число
a
и
процедура
проверки
повторяется.
После
нахождения
r
свидетелей
простоты,
выдается
ответ
«m,
вероятно,
простое»,
и
алгоритм
завершается.

Алгоритм
может
быть
записан
на
псевдокоде
следующим
образом:

Ввод:

число
проверяемое на простоту:
m
> 2
(нечётное
натуральное);

параметр,
определяющий
вероятность
ошибки теста r.

Вывод:

составное,
означает,
что
m
точно
составное;

или
вероятно
простое,
т.е. m
с
высокой
вероятностью
является
простым.

Представить
m
−
1
в
виде
2^s·t,
где
t
нечётно,
можно
сделать
последовательным
делением
m
— 1
на
2.

цикл
А:
повторить
r
раз:

Выбрать
случайное
a
в
диапазоне
[2,
m
−
2]

x
← a^t
mod
m

если
x
= 1
или
x
= m
−
1
то
перейти
на
следующую
итерацию
цикла
А

для
r
= 1
.. s
−
1

x
← x²
mod
m

если
x
= 1
то
вернуть
составное

если
x
= m
−
1
то
перейти
на
следующую
итерацию
цикла
А

вернуть
составное

вернуть
вероятно
простое

Из
теоремы
Рабина
следует,
что
если
r
случайно
выбранных
чисел
оказались
свидетелями
простоты
числа
m,
то
вероятность
того,
что
m
составное,
не
превосходит
4
^—
r.

Пример
выполнения проверки:

Проверяем
число m = 221.

Запишем
m − 1 = 220 как (2^2)·55, таким образом s = 2 и t
= 55.

Произвольно
выберем число a такое, что 1 < a < m-1,
допустим a = 174. Переходим к вычислениям:

Шаг
1. a^((2^0)·t) mod m = 174^55 mod 221 = 47 ≠ 1, или
m − 1

Шаг
2. a^((2^1)·t) mod m = 174^110 mod 221 = 220 = m − 1.

Так как
220 ≡ −1 mod m,
число 221 или простое (174 —свидетель
простоты числа 221)

или составное,
(тогда 174 ложный свидетель простоты).

Возьмём
другое произвольное «a», на этот раз
выбрав a = 137:

Шаг
1. a^((2^0)·t) mod n = 137^55 mod 221 = 188 ≠ 1, m − 1

Шаг
2. a^((2^1)·t) mod n = 137^110 mod 221 = 205 ≠ m − 1.

Т.е. 221
– составное.

Так как
137 свидетель того, что 221 составное, число
174 на самом деле было ложным свидетелем
простоты.

Задание

Выбрать два простых и два
составных нечетных числа (не кратных 3
и 5) и еще одно составное число Кармайкла.
Выбирать числа для выполнения задания
по следующей формуле:

1. Вычисляем:
X=((№ студента в
группе)+110)*23. Далее произвольно в диапазоне
X±20 выбрать нужные числа
(если в группе один студент, то проверяем
4-ые числа, если два, то 8, если три то 12).
Число Кармайкла выбирать по следующему
алгоритму:

студент в группе с номером
1. Берёт число 1105

студент в группе с
номером 2. Берёт число 1729

студент в
группе с номером 3. Берёт число 2465

студент
в группе с номером 4. Берёт число
2821

студент в группе с номером 5. Берёт
число 6601

студент в группе с номером
6. Берёт число 8911

для студентов с
большими номерами выбирать число
Кармайкла циклически, 7-й берёт опять
число 1105 и т.п. Сколько человек в бригаде,
столько разных чисел Кармайкла должно
быть проверено.

1. Проверить каждое из чисел
   тестом Рабина-Миллера. При выполнении
   задания в EXCEL выбирать k
   таком образом, чтоб вероятность принять
   составное за простое была не более
   0,0625. При программировании алгоритма
   выбирать k таком образом,
   чтоб вероятность принять составное за
   простое была не более 10^-3.

Ход
работы

X
= (25+110)*23= 3105

Простые
числа – 3119, 3121

Составные
числа – 3097, 3113

Число
Кармайкла – 1105

Алгоритм
проверки, реализованный на языке Python3

Результат
проверки чисел:

3119:

3121:

3097:

3113:

1105:

Санкт-Петербург

2021

Соседние файлы в предмете Математические основы защиты информации

• #
• #

  09.04.20231.28 Кб4Lab_09.py

• #
• #
• #
• #
• #
• #

  09.04.202311.87 Кб3Лаба 3.xlsx