Try out this Chinese Remainder Theorem problem, by hand: x = 3 mod 244 and x = 17 mod 495. Show all the steps of the process, including the extended euclidean algorithm. You can use the computer to do modular arithmetic for you (e.g. multiplying things if needed), but show the steps as if doing it by hand. Hand this in on the dropbox.

In preparation for class, try to solve 2x = 4 (mod 6). How many solutions are there? Can you give a generalizable theoretical proof your solution method is correct (not just an exhaustive check)?

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).

To Know: I’ll post the assessment for Module 2 (DLP and related cryptography and modular arithmetic) later tonight. I’m just finalizing it. You’ll have a week to do it.

To Do: Learn the Euclidean Algorithm! It’s easy, because I’ve made a video about it (13:28). Do as the video says (pause and think/try when it says). Note: if you aren’t feeling very comfortable with what the GCD (greatest common divisor) is, you may want to watch this video about GCD first (12:01) — not required, but there for you if you need it.

Then use the Euclidean algorithm to compute the gcd of 2266 and 822. Notice how the numbers are even always as you continue down (think back to the video for what is happening). Hand a neatly organized version of your work on the daily dropbox on canvas.

To Know: My plan is to post the Module 2 assessment on Wednesday, with one week to do it.

To Know: If you’re interested in the runtime of the Index Calculus, here are some course notes that cover it in more detail (from Andrew Sutherland’s MIT course on elliptic curves). This may be an interesting topic for a graduate student project: runtime for index calculus and/or index calculus improvements mod p and/or in other finite fields.

FOR GRADUATE STUDENTS: Please provide me by Friday (email is fine) a short paragraph description of what you intend to do for your written project for the course.

To Do: El Gamal Encryption Chain! Check out the El Gamal Tools. We will use the prime there (the next prime after 10^6), and the primitive root 2. This is set up on that tools page. Here are my notes from class on El Gamal; you’ll also find it in Section 7.5 of the 2nd edition of the text on canvas. Do the following:

Set up a private and public key for yourself. Publish the public key on the “#ciphertexts” channel on discord (Under Study Groups). Note your public and private key down on paper.

Choose a four-letter word as a message. It should be a polite, recognizable english word, so the decrypter will be able to tell they’ve done this correctly. It should answer, in some fashion, the question “What do you like?” Make notes on paper.

Find the most recent unused public key on there (if possible), and use the public key to encrypt your four-letter word to that person. (It will involve two chunks, so you will have to send them as two separate ciphertexts.) Keep notes on paper of the key steps.

Post your ciphertexts publicly for that person on the channel. Since it consists of two chunks, you should post two pairs (r,t).

When you receive a message from someone on the channel, decrypt it. Hopefully it is an english word. If it is, yay! Respond on the channel to that person to tell them the decryption you got. Keep notes on paper of the key steps.

For the canvas submission, show your notes from this work. If you don’t get someone sending you a message in time, that’s ok, but keep an eye out and do the decryption stage when possible.

To Know: I’ll post the assessment for Module 2 on Wednesday, with 1 week to do it. The topics include everything since Module 1, which is a lot of modular arithmetic, Discrete Log Problem and methods to solve it, Diffie-Hellman Key Exchange and El Gamal Encryption (which we’ll cover on Monday). I’ll give a more detailed list of topics shortly.

To Do:

Read Chapter 7, Section 7.2.3, which includes an example of Index Calculus (approximately 1.3 pages).

Use the Index Calculus Sage tools on the website (or your own purpose-written code) to implement Index Calculus to solve the discrete log problem 3^x = 71 (mod 127). You’ll probably want to do the linear algebra part by hand. You’ll probably want to pick B fairly small; experiment to make it easy for yourself.

To Know: This module has stretched a bit big, because there’s a lot of basic background (including runtimes, Big-Oh, lots about modular arithmetic) that we’ll build a lot of the course on. We still will talk about El Gamal and some methods for solving discrete log. I hope maybe to post the assessment early next week.

To Do: At the end of class today, I talked on the last slide about the “Birthday” attack on discrete log. The basic idea is to create two lists of elements and look for collisions (coincidences). Here is a scaffolded exercise:

To Know: The first assessment is 95% graded and you’ll get detailed solutions back, and then I’m happy to chat about the (unintionally) hard counting problem that was in there! Another day or two.

Play with the Big-O notation interactive (I think it’s fixed again now). In particular, read the text at the top of the page — it suggests a few small exercises. You need to click away from a box after changing something to get the graphs to update.

Please Read Section 3.6 (skipping 3.6.1 if you like) and 3.7 of your textbook. Please read actively.Everything here is considered part of the material we have covered. The book takes a somewhat different approach to the modular arithmetic, so this is at once the same material we have been covering, and a different take on it. One thing that is new and we will come back to, is the formula for Euler’s phi-function. The book does it depending on the chinese remainder theorem, which we haven’t covered yet, so you can skip the justification, but it is nice to look at and be able to use the formula. The rest should look like a bit of a remix of things we’ve seen. Take the time to line it up, conceptually, with the things we’ve seen (particularly the “sum-up” from the last lecture).

To hand in:

(1) Use the formula for Euler phi from the book to compute phi(15) and phi(45), showing your work.

(2) Tell me three things you learned from the reading.

To Know: If you want/need an “invite link” for the ebook version of the text, it is now listed in canvas on the main page. You shouldn’t need this, but you may find it useful if you bought the ebook version. It allows you to use a special editor for reading your purchased ebook.

To Know: On canvas, you currently have access to Chapters 2, 3 and 7. Chapter 3 has background on modular arithmetic (but without much explanation/intuition). Chapter 7 is about discrete log.

Today’s daily post is a series of exercises.

Compute 2^10223 modulo 101 by hand, showing your work (this shouldn’t be laborious). Hint: use the fact that 101 is prime to reduce the exponent with respect to a known modulus, then use repeated squaring.

These next ones go together (do these by hand):

What is the multiplicative order of 7 mod 4?

Compute 7^7 mod 4 by hand (hint: use above)

Compute phi(10) (that’s Euler phi function).

What is the multiplicative order of 7 mod 10?

What is the last digit of 7^(7^7)?

Use Sage to compute 2^110 modulo 111. Based on the answer, tell me why you can conclude 111 is not prime.

Here’s another multi-stage problem:

Ask Sage to do this: p = next_prime(10); p This computes the next prime after 10.

Next, in the next cell, ask Sage to do this: Mod(3,p)^(p-1) Explain the result.

Next, in the next cell, ask Sage to do this: Mod(3^(p-1),p) Explain the result.

Next cell, ask Sage to do this: p = next_prime(10^240); p This is a much bigger prime, and it takes Sage a moment to find it.

Next, in the next cell, ask Sage to do this: Mod(3,p)^(p-1) Explain the result.

Next, in the next cell, ask Sage to do this: Mod(3^(p-1),p) Explain the result.

By hand, using Gauss’ algorithm demonstrated in class, compute the inverse of 107 modulo 311. Here are notes from class today.

Compare your result to the result the computer provides using the Gauss Modular Inverse tool (which you will always be able to find in the website left-hand menu).

If you didn’t get it right, or your version took more steps, revisit it with another example: 40 modulo 311. Keep at it until you feel confident in your ability to do this correctly by hand.

Recall the exercises on DLP from the weekend. Please revisit these and compare to the solutions posted here. Make sure you are comfortable doing these exercises.

Revisit the algorithm you created for the last problem: finding the discrete logarithm of h modulo p, with respect to primitive root g. If you didn’t succeed at creating this algorithm, take a look at my solutions.

Now modify this algorithm so that it computes random powers of g until it happens to hit h. Have it output the total number of random guesses it needed to make before it hit h. You might want to use the Sage function randint(L,H) which returns a random integer between L and H inclusive.

Run a series of tests for different size prime p (the modulus), and various h. Note: you can find a primitive root mod p using the Sage command primitive_root(p). Make a conjecture as to the expected number of random guesses before finding h.

To hand in online: some evidence of your work above (e.g. sage code/data & guess and/or by-hand inverse computation examples).

To Know: Please use PDF, PNG or JPG formats to upload files to canvas dropboxes. Don’t ZIP or compress files. Multiple files are fine. Please make sure they are readable. There are apps like CamScanner that turn photos into nice high-contrast PDFs.

To Know: Sorry I haven’t gotten to the “biggest number” thing yet, I promise we will! 🙂

Spend a bit more time with the last daily task exercises if you had trouble with it — in particular, contact me for some personal help and advice if needed. I think for some this was quick, but for others Sage was frustrating and I’d like to help.

To hand in today: a check-in. Just a quick note about how the course is going for you and if you are frustrated/happy or have any particular concerns. A sentence or two suffices.