Правилен ли алгоритм проверки простоты Рабина-Миллера с использованием модульного возведения в квадрат?

Недавно я наткнулся на этот фрагмент кода для алгоритма Рабина-Миллера, описанный здесь:

from random import randint

    def _bits_of_n(n):
        """ Return the list of the bits in the binary
            representation of n, from LSB to MSB
        """
        bits = []

        while n:
            bits.append(n % 2)
            n /= 2

        return bits

    def _MR_composite_witness(a, n):
        """ Witness functions for the Miller-Rabin
            test. If 'a' can be used to prove that
            'n' is composite, return True. If False
            is returned, there's high (though < 1)
            probability that 'n' is prime.
        """
        rem = 1

        # Computes a^(n-1) mod n, using modular
        # exponentation by repeative squaring.
        #
        for b in reversed(_bits_of_n(n - 1)):
            x = rem
            rem = (rem * rem) % n

            if rem == 1 and x != 1 and x != n - 1:
                return True

            if b == 1:
                rem = (rem * a) % n

        if rem != 1:
            return True
        return False

    def isprime_MR(n, trials=6):
        """ Determine whether n is prime using the
            probabilistic Miller-Rabin test. Follows
            the procedure described in section 33.8
            in CLR's Introduction to Algorithms

            trials:
                The amount of trials of the test.
                A larger amount of trials increases
                the chances of a correct answer.
                6 is safe enough for all practical
                purposes.
        """
        if n < 2:
            return False

        for ntrial in xrange(trials):
            if _MR_composite_witness(randint(1, n - 1), n):
                return False

        return True

Я знаю, что тест RM должен принимать N, разлагать N-1 = t*(2^s), а затем пытаться найти такое, что a^t != 1 и a^((2^r)t) != -1 для всех 0 ‹= r ‹ s

Но этот алгоритм делает что-то другое. Это отчасти напоминает мне алгоритм Ферма, где мы проверяем a^(n-1) mod n == 1, так как он использует возведение в квадрат и умножение, чтобы получить a^(n-1), но проверяет, конгруэнтны ли какие-либо из промежуточных результатов 1 мод н.

Я не понимаю, как эти 2 эквивалентны, не могли бы вы объяснить, почему (x^2==1 и x!= ​​1 и x!=n-1) работает как достаточное условие?

Спасибо!


python algorithm algebra primes
person michnovka    schedule 30.05.2015    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Если мы находим промежуточный результат, конгруэнтный 1 (по модулю n) и такой, что предыдущий результат x не конгруэнтен 1 или -1 (т.е. n-1) по модулю n, то это число x является нетривиальным квадратным корнем из 1 по модулю n (т. е. число x такое, что x ≠ -1, 1 mod n, но x^2 = 1 mod n). Это означает, что n составное.

Доказательство: предположим, ради противоречия, что x ^ 2 конгруэнтно 1 по модулю p, x не равно 1 или -1 по модулю p, и p простое число. Это эквивалентно утверждению, что p делит x^2 - 1 = (x-1)(x+1). Следовательно, поскольку p простое число, p делит x-1 или x+1, что означает, что x конгруэнтно 1 или -1 по модулю p.

Вот почему (x^2==1 и x != 1 и x!=n-1) является достаточным условием - это сразу означает, что n составное. Таким образом, мы можем остановить алгоритм раньше, чтобы сэкономить время вычислений.

Как указано в вашей ссылке (с опечаткой), хорошее объяснение этого можно найти в разделе 31.8 Введения в алгоритмы Кормена, Лейзерсона, Ривеста и Штейна, и некоторые из моих ответов адаптированы из этой книги.

person user2258552    schedule 30.05.2015