Problem 1: Use the randint command, along with the jacobi_symbol and power_mod command to write code for the function SolovayStrassen(n,k) which tests n for primality using the Solovay Strassen Test k times and returns false for composite and true for probably prime.

def SolovayStrassen(n,k):

for i in [1..k]:

Check that your function works by testing whether 8675309 and 8675307 are prime using the fermat function and several different bases. Which one is prime?

Problem 2: Use the randint command, along with the power_mod command to write code for the function MillerRabin(n,j) which tests n for primality using the Miller-Rabin Test j times and returns false for composite and true for probably prime.

def MillerRabin(n,j):

m=odd_part(n-1) #stores the odd part of the n-1 required for Miller Rabin

k=log((n-1)/m,2) #stores the number of times 2 divides n-1

for h in [1..j]: #this loop is for the number of times that you run the test

Problem 3 Use randint and one of your primality tests (you may need to use a while loop or something else!) to generate two random prime numbers p and q with 60 digits.