import random
import math

x=8
y=2
N=3
def modexp(x,y,N):
    if (y==0):
        return 1
    z= modexp(x,(y/2),N)
    if y%2 == 0:
        return (z*z)%N
    else:
        return (x*z*z%N)
print (modexp(8,3,3))

def primality2(N,k):
    y = N-1
    for i in range (0,k):
        x = random.randint(2, N-1)
        ##print x
        if modexp(x,y,N) !=1:
            return "not prime"
    return "prime"

count = 0
for i in range (0,1000):
    result = primality2(1729,10000)
    if result == "prime":
        count +=1
print count

Given inputs N and k, you should determine whether N is prime or not using k trails. Print N "is prime" or N "is not prime".
Part 2

Carmichael numbers are composite numbers that pass fermat's little theorem for all integers aa relatively prime to NN. For each of the following Carmichael numbers determine the probability of failure in k trials, using k=1000. That is, the probability that the number is determined to be a prime when in fact it is not.