Task 1: Write Python functions modexp1(a,n,m), modexp2(a,n,m), and modexp(a,n,m) to compute a^n mod m using the 3 algorithms we described in class. Namely modexp1 just computes a^n first with n-1 multiplications and takes it mod m, modexp2 computes a^j mod m for each j up to n, and modexp uses repeated squaring (and takes this mod m at each step).

In addition, here is a fourth way to compute a^n mod m: you can use Python's native exponentiation function (don't in the above algorithms) a**n % m, where the double asterisk denotes exponentiation and the percent is mod.

For the repeated squaring method, you will need to determine the binary representation of n. You can either do this by using division by 2 and mod 2, or you can use bitwise operations.

For each of these 4 methods, compute 3^m mod m various values of m, and determine around what point (in terms of the number of digits of m) this method becomes slow (say, takes more than a couple of seconds).

Task 2: Design an algorithm for and write a function isprime(n), which will return True if n is prime and False otherwise. Test this on various n, in particular, n of the form 11, 101, 1001, 10001, ... After about how many digits does this algorithm become slow?

Task 3: Recall the function randint(a,b), which returns a random integer between a and b (inclusive). Using this, and the isprime function, estimate the probability that a random k-digit number is prime, for k between 2 and 10. (For small you can test all the possibilities. For larger k, sample a sizable number of random k-digit integers.)

Task 4: Design and algorithm for and write a function factor(n) that will factor a positive integer n. Return the factors of n as a list. Repeat factors to represent prime powers. For instance, if n = 60, you should return the list [2, 2, 3, 5]. If your list does not come out in order by nature of your algorithm, you can use the sorted function to sort your list before you return it.