def miller_rabin(n,p):
        small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
        if n < 2: return False
        for p in small_primes:
                if n < p * p: return True
                if n % p == 0: return False
        r, s = 0, n - 1
        while s % 2 == 0:
                r += 1
                s //= 2
        for _ in range(p):
                a = randrange(2, n - 1)
                x = pow(a, s, n)
                if x == 1 or x == n - 1:
                        continue
                for _ in range(r - 1):
                        x = pow(x, 2, n)
                        if x == n - 1:
                                break
                else:
                        return False
        return True

n=13
p=80
print "miller_rabin(",n,",",p,")=",miller_rabin(n,p)

def generate_prime(k,p):
#       MR = False
#       while(MR == False):
#               s = random.randint(0, 2**k -1)
#               MR = miller_rabin(s,p)
        return 2

k=100
p=80
prime=generate_prime(k,p)
print "generate_prime(",k,",",p,")=",prime
print "nombre de bits:", floor(log(prime,2))+1