560.valuation(2)

1979.valuation(3)

100000000000.valuation(5)

randrange(1,1105) #most likely we will get a different number each time

randrange(1,1105)

gcd(1105,1103)

gcd(1105,919) #more often than not, it will be relatively prime, consider totient formula.

def finding(n):
    a=(randrange(2, n))
    print (a)
    if gcd(a,n)==1:
        print "run Miller2"
    else:
        print "run valuation test again"

finding(15)

def Miller2(n, a): #a and n found above
    k=(n-1).valuation(2)
    q=(n-1)/2^k
    if (a^q, n)!=1: #this is the first part of the code.
        c=0
        for i in range(0, k):
            if Mod(a^(q*2^i), n)!=-1:
                c=c+1
        if c==k:
            print 'composite'
        else:
            print 'test is inconclusive'
    else:
        print 'test is inconclusive'

Miller2(15, 11)

finding(561)

Miller2(561,70)

finding(1105)

Miller2(1105,223)

finding(294409)

Miller2(294409,191033)

finding(8675309)

Miller2(8675309,7509281)

finding(118901521)

Miller2(118901521,18801468)

finding(104395303)

Miller2(104395303,42564411)

#Good job. 24/25 (comments on the proof are in the print-out from your email.) - Adriana.