Reputation: 3399
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
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