So we're reviewing the Miller-Rabin test, for homework we had to do this:
Code
import random
#Define a Python function G(t,n) that returns '1' if t is equivalent to
#1 modulo n, returns '-1' if t is equivalent to -1 modulo n, and returns
#'*' otherwise.
def G(t,n):
if t%n == 1: return 1
if t%-n == -1: return -1
return '*'
#Define a Python function seeG(L,n) that takes a list L of numbers and prints
#out, on one line, the characters G(t,n) for t in L.
def seeG(L,n):
for t in L:
print G(t,n),
#Define a Python function sd(n) that returns the list [s,d], or the pair
#(s,d), where d is odd and n-1 = 2^s*d.
def sd(n):
d = n-1
s = 0
while d%2 == 0:
s += 1
d /= 2
return [s,d]
#Define a Python function MR(n) that creates a random number a between 2 and
#n-2, sets x equal to pow(a,d,n), and returns the list
#[x,pow(x,2,n),pow(x,4,n),...,pow(x,2**s,n)]. Here d and s are the numbers
#returned by sd(n).
def MR(n):
a = random.randint(2,n-2)
s_d= sd(n)
x = pow(a, s_d[1], n)
MR = [x]
for s in xrange(2, pow(2,s_d[0])+1, 2):
MR += [pow(x,s,n)]
return MR
#Define a Python function seeMR(n) that prints out the list returned by MR(n)
#using seeG(L,n).
def seeMR(n):
L = MR(n)
seeG(L,n)
#Apply seeMR(n) ten times to various large Carmichael numbers n, such as
#56052361. What do the results mean? You can find large Carmichael numbers
#here. The ones with no small factors are the most stubborn ones.
for i in xrange(10):
seeMR(56052361)
print
...but I don't think it's working properly. I have no idea what could be wrong with it. Please if you know math and can read python help me out! (#'s are just comments; what we're supposed to do)
Thank you!
Will pay if desired!
e/ Sample output:
Code
1 1 1 1 1
* * 1 * 1
* * 1 * 1
* 1 1 1 1
* * 1 * 1
* * 1 * 1
* 1 1 1 1
* * 1 * 1
* * 1 * 1
-1 1 1 1 1
This post was edited by DeadlySanity on Mar 25 2013 11:38pm