michnovka
michnovka

Reputation: 3399

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

I have recently come across this piece of code for Rabin-Miller algorithm, as decribed 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

I know that RM test should take N, decompose N-1 = t*(2^s) and then try to find a such that a^t != 1 and a^((2^r)t) != -1 for all 0 <= r < s

But this algorithm does something different. It reminds me partly of Fermats algorithm, where we test a^(n-1) mod n == 1, as it uses square and multiply to get a^(n-1) but checks if any of the intermediate results are congruent 1 mod n.

I do not see how these 2 are equivalent, can you please explain why (x^2==1 and x != 1 and x!=n-1) works as a sufficient condition?

Thanks!

Upvotes: 4

Views: 359

Answers (1)

user2258552
user2258552

Reputation: 822

If we find an intermediate result that is congruent to 1 (modulo n) and such that the previous result x was not congruent to 1 or -1 (i.e. n-1) modulo n, then this number x is a nontrivial square root of 1 modulo n (i.e. a number x such that x ≠ -1, 1 mod n but x^2 = 1 mod n). This means that n is composite.

Proof: Suppose for the sake of contradiction that x^2 is congruent to 1 modulo p, x is not 1 or -1 modulo p, and p is prime. This is equivalent to saying that p divides x^2 - 1 = (x-1)(x+1). Therefore, since p is prime, p divides x-1 or x+1, which means that x is congruent to 1 or -1 modulo p.

This is why (x^2==1 and x != 1 and x!=n-1) is a sufficient condition - this immediately implies that n is composite. Thus we can stop the algorithm early to save computational time.

As your link states (with a typo), a good explanation of this is found in section 31.8 of Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, and some of my answer is adapted from that book.

Upvotes: 3

Related Questions