python - 使用模平方的 Rabin-Miller 素数测试算法是否正确？

Question

我最近遇到了这段 Rabin-Miller 算法的代码，如描述的那样 here :

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

但是这个算法做了一些不同的事情。它部分让我想起了 Fermats 算法，我们在其中测试 a^(n-1) mod n == 1，因为它使用平方和乘法得到 a^(n-1) 但检查是否有任何中间结果是一致的 1国防部

我看不出这 2 个是等价的，你能解释一下为什么 (x^2==1 and x != 1 and x!=n-1) 可以作为充分条件吗？

谢谢!

Answer 1

如果我们找到一个与 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 and x != 1 and x!=n-1) 是一个充分条件——这直接意味着 n 是合数。因此我们可以提前停止算法以节省计算时间。

正如您的链接状态(有错别字)，在 Cormen、Leiserson、Rivest 和 Stein 的《算法简介》第 31.8 节中可以找到对此的一个很好的解释，我的一些回答改编自那本书。