# Question: what is the time complexity in big oh of pythons...

###### Question details

What is the time complexity in Big Oh of python's built in modular exponentiation function using pow? Ex: pow(a, b, c)

Assume that both k and n are n bits for simplicity sake

Assume that division is O(n^2)

Assume that multiplication is O(n^2)

Assume that mod is O(n)

Here is my code:

def run_fermat(n, k):

if n == 1 or n == 0: # O(1) return 'composite' for i in range(0, k): # Here we look at k in n bits a = random.randint(1, n - 1) # O(1) if pow(a, n-1, n) != 1: # Modular exponentiation - this is faster than using our mod_exp function return 'composite' # Number is not prime return 'prime' # Number is prime