To Know: Assessment for Module 2 is open and due on Wednesday.

Next up is to learn the Extended Euclidean Algorithm: video (10:58). Use it to solve the following linear Diophantine equation, to find one solution in integers x and y: 440x + 377y = 1. Write it up neatly.

Using Sage to do a single modular exponentiation, use the Fermat Primality Test to test if n = 3057601 is composite or probably prime, using the base 99908. Write down what you computed and what you conclude.

Next, using the Miller-Rabin Tools, implement the Miller-Rabin primality test to test if n = 3057601 is composite or probably prime, using the base 99908. (These are the same numbers as above.) Write out the steps (the b_i’s and how you calculate them and what you observe and conclude).