AAACET Prime Numbers Fast Exponentiation Using Python Exercise

Comment must be added.

Q1 [30 pts] Mersenne prime: is a prime number of the form Mp = 2^p – 1, where p is
a prime number. For example, M5 = 2^5 – 1 = 31 is a Mersenne prime. Notice
that if p is not prime, then 2^p – 1 must be composite. To generate a Mersenne
prime of a large size, take a small prime p, then compute n = 2^p – 1, use
primality test to check if n is prime. If so, then n is Mersenne prime of length p
bits. Otherwise, n is called a Mersenne composite. Implement a Boolean
function mersenne (p) that returns true if and only if Mp is a Mersenne prime.
The function should call your primality test function is_prime (with k bases
shown below).
a) In the main program, use your function to print all the Mersenne primes
Mp for p between 2 and 29, (with k = 3 in the is_prime function).
b) Repeat part (a) using k =1 (for base 2 only), and compare the results
c) Report the outcomes of this experiment (in the PA2.report.pdf file)
d) Test mersenne (31). How long does it take to test if M31 is a Mersenne
prime? Report your observations with justification if any.

Q2 [40 pts] Implement the modular exponentiation (a.k.a. fast exponentiation)
function mod_exp (b, n, m) to compute b^n (mod m) more efficiently. (Hint: to
read n bit-by-bit, use / and % operations repeatedly)
a) Test your function for b = 3, n = 2^31 – 2, m = 2^31 – 1.
b) Report the result and the time (in seconds) it takes to find the result

Q3 [30 pts] Modify your is_prime function to use the mod_exp (b, n, m) instead of
the standard power operation (b**n % m). Rename it as is_prime2. Modify the
mersenne (p) function to use is_prime2, and call it mersenne2.
a) Use the modified function mersenne2 to print all the Mersenne primes
Mp for p between 2 and 31 if possible, (with k = 3 in the is_prime
function). Compare the results with the ones found in Q1.
b) Gradually increase the range of p to find more Mersenne primes (say up
to p = 101 if possible). What is the largest Mersenne prime you can
achieve here?
c) Extend the work in part (b) and find the maximum Mersenne prime you
can get from this experiment in a reasonable amount of time (Say
within two minutes).
d) Report your findings in this experiment, and comment on the speed up
achieved by implementing the fast exponentiation algorithm.

—————

the code must be built on top of the below code:

my_Primes = [2, 3, 5, 7, 11, 13, 17, 19]
def is_prime(n, k):
if n in my_Primes:
return True

# Fermat Theorem: if p prime, then b^(p-1) = 1 (mod p)
# choose a base b co-prime to n, if b^(n-1) mod n != 1 then Not Prime
for i in range (k): # i = 0,1,2, …, k-1
base = my_Primes[i]
if gcd(base, n) > 1 :
return False
elif ((base**(n-1)) % n) > 1 :
return False

return True #pseudoprime to all bases tested.

# Main Program:

for j in range (2, 2000):
if is_prime (j, 3): # for k= 3, accuracy ~99.95%
# for k= 2, accuracy ~99.90%
counter += 1
print (j, end = ” t”)
print (“nDone!”)