You may import the following library functions in your module:

from fractions import gcd

from math import log

from math import floor

'You may also use:

the built-in pow() function to compute modular exponents efficiently (i.e., ak mod n can be written in Python as pow(a,k,n)),

You may also need to import your hw3 (will be attached below)

5. Implement a function makePrime(d) that takes a single integer argument d where d >= 1 and returns a probably prime number that has exactly d digits. Your implementation should be sufficiently efficient to produce an output for d = 100 in a reasonably short amount of time. Implementations that perform an exponentially large exhaustive search, even if the algorithm is mathematically correct, will not earn full credit.

>>> makePrime(2)

47

>>> makePrime(100) 3908330587430939367983163094172482420761782436265274101479718696329311615357177668931627057438461519

hw3 functions

def closest(t, ks): """takes 2 arguments a target t and list of ints ks and returns in k in ks that is closes to t""" return min(ks, key=lambda p: abs(p-t))

def findCoprime(m): """takes a single positive int m and returns an int b where b > 1 and b is coprime with m"""" for i in range(2,x): if math.gcd(i, x) == 1: return i

def randByIndex(m, i): """takes 2 positive integer arguments m represents the upper bound of random numbers generated and i represents a index specifying which random number in the sqeuence should be generated""" return (i * findCoprime(n)) % n