//Miller-Rabin (Primality Test)
import random
def power(x,n):
if(n==0):
return 1
elif(n%2==0):
return (power(x,n//2)*power(x,n//2))
else:
return (x*(power(x,n//2))*(power(x,n//2)))
def millir(n,d):
a=2+random.randint(1,n-4)
x=(power(a,d))%n
if(x==1 or x==n-1):
return True
while(d==n-1):
x=(x*x)%n
if(x==1):
return False
if(x==n-1):
return True
def isprime(n,k):
if(n==1):
return False
if(n==2):
return True
if(n%2==0):
return False
d1=0
for d in range(3,10000,2):
for r in range(1,10000):
if(n-1==d*(2**r)):
d1=d
break
if(d1==d):
break
for i in range(2):
if(millir(n,d)==False):
return False
return True
print(isprime(21,2))
0 Comments