this lab involves some basic number theory that is relevant to rsa.

task 1: write a function binrep(n), which given a non-negative integer n returns the binary representation of n as a list of bits. e.g., binrep(6) should return the list [0,1,1]. (the lowest order bits should come first). you may implement this using division and mod or using bitwise operators.

task 2: write a function bintab(N) which prints a table of the non-negative integers up to N together with their binary representations. e.g., bintab(4) should print something like

0    0
1    1
2   10
3   11
4  100

you format things a bit differently, but try to make the table look reasonably nice and right align both columns. note that you can print k spaces with print(' '*k). test your function for N=20.

task 3: write a function bits2int(b) which is the inverse of binrep(n), i.e., given a list of bits b, this should return the corresponding integer. using a loop, check that bits2int(binrep(n)) == n for n between 0 and 1,000,000.

task 4: write a function gcd(a,b) that implements the euclidean algorithm with division (the euclidean algorithm as presented in section 7.3 of the text) that returns the gcd of two integers not both 0. if a and b are both zero, either return 'infinity' or an error. test out gcd(14,7), gcd(14,21), gcd(-14,21), gcd(12,0) and gcd(2**200+1, 10**100+1). try timing the last example using timeit. e.g., in interactive mode the following will tell you how many seconds it takes to run that example 1000 times:

from timeit import timeit
timeit(lambda: gcd(2**200+1, 10**100+1), number = 1000)

task 5: write a function extendgcd(a,b) that implements the extended euclidean algorithm to return a triple (x,y,d) where d is the gcd and x and y are some integers such that ax+by=d. test your code on the examples (a,b) = (14,7), (a,b) = (14,21), (a,b) = (201, 37) and (a,b) = (2**200+1, 10**100+1).

task 6: write a function modinv(a,n) that uses your extendgcd function to quickly compute and return the inverse of a mod n. if a is not invertible mod n, either return -1 or raise an error. recall or rewrite your function invert(a,n) from lab 2 which computes the same thing by trial and error (brute force). check that both functions give the same result for some small values of a and n. then time both functions for a=2 and n=2**m+1 where m = 5, 10, 15, 20, 25, 30.

remark: the invert function should get slow so you can run timeit with number = 1 or something like 3 or 5 if you prefer. the point in general of timing many repetitions of code is to get an average runtime--if you try timeit on a function with number = 1 several times, you should see some variation due to what else is going on in the computer, etc. if the actual runtime of your function is fast (fractions of a second), then these small variations will percentage-wise affect your timing by quite a bit. but if the actual runtime of your function is quite slow (say, on the order of seconds or longer), than the variation will be relatively small, so there is less meaning in averaging the time over 10000 trials, say.

lab 5 homework: complete the above tasks (due fri mar 6)