Please give a detailed solution to this problem. A randomized primality testing
ID: 3787928 • Letter: P
Question
Please give a detailed solution to this problem.
A randomized primality testing algorithm with low error probability is given below function primality2(N) Input Positive integer N Output yes /no Pick positive integers a 1, a2, ak N at random if a N-1 1 (mod N) for all i 1, 2 return yes else: return no Implement the above algorithm using the modexp function in the code below for modular exponentiation. (z, y, N) function mode Input Two n-bit integers z and N, an integer exponent y Output mod N if y 0: return 1 modexp(r, Ly/2, N) if y is even return 22 mod N else return r 22 mod NExplanation / Answer
Below is the python code as per requirements.
For code in your browser visit this url: http://code.geeksforgeeks.org/s25MDr
made sure that most of the code is well commented. In case of doubts revert back through comments.
points to remember:
=>Time complexity of this solution is O(k Log n). Note that power function takes O(Log n) time.
=>Note that the above method may fail even if we increase number of iterations (higher k).
=========================================================================
#code
import random
'''
If n is prime, then always returns true, If n is
composite than returns false with high probability
Higher value of k increases probability of correct result.
'''
def Primality2(n,k):
if (n <= 1 or n == 4):
return False
if (n <= 3):
return True
#Try k times
while (k>0):
#Pick a random number in [2..n-2]
#Above corner cases make sure that n > 4
a=random.randrange(2,n-1);
#Fermat's little theorem
if (modexp(a, n-1, n) != 1):
return False
k-=1
return True
#Iterative Function to calculate (a^n)%p
def modexp(a,n,p):
res = 1 #Initialize result
a = a % p #Update 'a' if 'a' >= p
while (n > 0):
#If n is odd, multiply 'a' with result
if (n%2==1):
res = (res*a) % p
#n must be even now
n = n>>1 #n = n/2
a = (a*a)%p
return res
if(Primality2(12,3)):
print('isprime')
else:
print('isnotprime')
===========================================================================