使用模平方的 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 mod n。

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

谢谢！

Answer 1

如果我们找到一个与 1 (modulo n) 一致的中间结果，并且之前的结果 x 与 1 或 -1（即 n-1）不一致 modulo n，那么这个数字 x 是 1 modulo n 的非平凡平方根（即一个数字 x 使得 x ≠ -1, 1 mod n 但 x^2 = 1 mod n).这意味着 n 是合数。

证明：为了反证，假设x^2与1modulo p全等，x不为1或-1modulo p，且p为质数。这相当于说 p 除 x^2 - 1 = (x-1)(x+1)。因此，由于p是素数，p整除x-1或x+1，即x全等于1或-1modulo p.

这就是为什么 (x^2==1 and x != 1 and x!=n-1) 是一个充分条件——这直接意味着 n 是合数。因此我们可以提前停止算法以节省计算时间。

正如您的 link 所述（有错别字），在 Cormen、Leiserson、Rivest 和 Stein 的算法简介的第 31.8 节中可以找到对此的一个很好的解释，并且我的一些答案被改编来自那本书。

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

Is Rabin-Miller primality test algorithm using modular squaring correct?

python

algorithm

primes

algebra