The Module 2 Test is on Friday in class. First and foremost, please study for that.

The test covers Module 2 and also covers part of Module 1. Written test, no calculators or cheat sheets. I will include the mod 26 addition/multiplication tables in the test packet. See the Goals page for a list of topics (those with checkmarks; that’s all updated). Textbook review questions are listed under Modules 1 and 2 on that page.

I will have an office hour on Thursday at noon on the classroom zoom link (available on discord and canvas). I will try to be especially available on discord.

Useful tips: You can click “archive” in the top bar for a day-by-day list of notes (my written notes from class) and resources. All lecture recordings (except one) are available on canvas.

As something to upload to canvas for today’s daily, please make sure your daily post evaluation sheet is up to date and upload a copy of that.

The Module 2 Test is on Friday in class. It also covers part of Module 1. Written test, no calculators or cheat sheets. I will include the mod 26 addition/multiplication tables in the test packet. See the Goals page for a list of topics (those with checkmarks; I’ll further update the checkmarks after Wednesday’s class, depending on what we manage to cover). Textbook review questions are listed under Modules 1 and 2 on that page.

I will have an office hour on Thursday at noon on the classroom zoom link.

You can find some index calculus examples that work out nicely in this replacement video (9:18), its accompanying notes, and in the course notes I’m writing (currently section 2.8.3). Please use these as resources rather than the live lecture video where I made and had to correct errors.

Solve the discrete logarithm problem for $p=131$, $g=2$, $h=17$, using the Index Calculus method. You may use the Index Calculus Tools and Sage’s modular arithmetic and plain arithmetic computations to avoid by-hand computations, but please solve the linear system by hand (i.e. choosing which equations to subtract from which etc.). Note: this is a randomized algorithm, so you will get different relations than someone else, or next time you run the tool. If you are not finding a very nice linear system, just try to get some more relations and pick simple manageable ones.

Please spend the remainder of your time studying for the Module 2 Test on Friday.

ANNOUNCEMENT: The first assessment will be a full-period in-class test on Module 2 and portions of Module 1, on Friday September 16th, 2022. As we finish up information I am updating the Goals page with checkmarks. Checkmarks indicate material that will be covered. It will involve demonstrating the ability to reason about material covered, to implement algorithms by hand, and to do small mathematical proofs (some proofs, like that of Euler’s theorem, should be studied so you can reproduce them).

Compare your solutions for daily posts due Sept 2, Sept 7 and Sept 9. Look these over carefully (this is a great learning opportunity!) and ask if you have questions.

Use exhaustive search or any method to compute $L_2(3)$ modulo $13$. You can use Sage’s modular arithmetic functions such as the tables on this page.

It is a fact that $p=101$ is prime, and $2$ is a primitive root modulo $p$. It is a fact that $L_2(3)=69$ and $L_2(5)=24$ modulo $p$. It is also a fact that the integer factorization of $24$ is $24 = 2^3 \cdot 3$. Using these facts, evaluate $L_2(24)$ modulo $p$ with minimal work (just combine the facts above).

We finished class Friday before I could do an example of the Baby-Step-Giant-Step algorithm. Please check the notes (which have an example) or watch this video of the example (3:22), and review the method. I’ve now added it to the latex course notes. Your text also has a discussion (Chapter 7, Section 7.2.2 in 2nd ed).

Use the Baby-Step-Giant-Step algorithm (and show all steps) to solve the discrete logarithm problem $34 = 3^x \pmod{113}$. You may use Sage’s functionality to compute the lists, including the tools on the BabyStepGiantStep page if you want to (ask for help on discord if you need some explanation of the page), so it shouldn’t involve much work by hand. But please present the solutions tidily and in a well-explained and well-labelled way (indicate where each term in each list comes from, not just the value you get), so the algorithm is evident.

Analyse the runtime of the Baby-Step-Giant-Step algorithm. That is, clearly answer the following. This is similar to what we did for modular exponentiation in class (see the notes from class).

What is the input?

What is the size of the input?

What is the runtime?

What is the runtime as a function of the input size?

For each of the following pairs of functions, determine if $f=O(g)$ and if $g=O(f)$.

$f(x) =|sin(x)|$ and $g(x) = 1/2$.

$f(x) = 2^x$ and $g(x) = 3^x$.

Read your textbook, Section 2.9 “One Time Pads”. This explains the “add your message to the shared key” approach I used in the last daily post. (Let me know if you don’t have access to the text yet.)

Fill in this Google Form collecting some info on how you want to do office hours and whether you want some extra tutorial on proofs.

A bit of math practice that shows that the parity (even or oddness) of the discrete log can be discovered easily. Let $p$ be a prime number.

Show that if $ab \equiv 0 \pmod p$ then $a \equiv 0 \pmod p$ or $b \equiv 0 \pmod p$

Use part (1) on the expression $(x+1)(x-1)$ to show that the only two solutions to $x^2 \equiv 1 \pmod p$ are $1$ and $-1$.

Let $g$ be a primitive root mod $p$. Show that $g^{(p-1)/2} \equiv -1 \pmod p$. (This uses the previous part.)

Suppose $h \equiv g^x \pmod p$ is given to you (but $x$ is not known). Show how you can determine if $x$ is even or odd. Hint: Raise the equation $h\equiv g^x \pmod p$ to the $(p-1)/2$ power and see what you get using the previous part.

Note that $2$ is a primitive root modulo $11$. Use the test above to determine if $x$ so that $2^x \equiv 5 \pmod{11}$ is even or odd.

Check whether you are correct by finding $x$ (by any method).

Comment on the runtime of this test for the parity of $x$.

If you are so inclined, try to break one of the ciphertexts on discord from our Diffie-Hellman Key Exchange. We discussed this in class and saw that the Sage server wasn’t having it, with my little for loop. But maybe you can make it work!

Today you will perform a Diffie-Hellman Key Exchange in order to send a message to someone on the #ciphertexts channel. Big picture: you’ll do a Diffie-Hellman Key Exchange to make a shared secret and then use that shared secret as a key for a very simple encryption (a sort of Caesar Cipher or One-Time Pad):

Create a secret message which is at most 6 letters long. It should answer “Why CU?” Please don’t make it longer or this exercise won’t work. Use only the 26 letters of the alphabet, but you can use lower or upper case.

Turn it into an integer using the Text to Integer tool. (This turns it into an integer by writing the letters in ASCII and making an integer base 255 with those digits. There’s an Integer-to-Text tool on the same page to undo this process.)

If you need a review of Diffie-Hellman, check the lecture notes/video and Section 7.4 of the textbook.

We will use prime $p=10^{15}+37$, and its primitive root $g=2$. The first box in the Diffie-Hellman Tools page will initialize this modular ring for you.

Use the Diffie-Hellman Tools (second box) to find a random secret a. We’ll call this your secret key. Keep it secret, maybe in your underwear drawer. (Joking! — actually safer if you copy it into a text file on your computer, because if you write it by hand you’ll make an error.)

Compute $g^a$ using the Diffie-Hellman Tools third box (no need to do this by hand!) We’ll call this your public key.

Announce your public key on discord #ciphertexts.

Find someone else’s public key ($g^b$) on discord. Let’s call that other person Bob. Use it to generate your shared secret ($g^{ab}$) with Bob (you’ll need your secret key for this). Again, you can use the third box in the Diffie-Hellman Tools page to do the computations (no need to work by hand).

Add the shared secret to your message mod p. Announce the result on discord as the secret message for Bob. Include your public key for them, because they will need it. You post might look like “My message for @soandso is X and my public key is Y.”

When someone sends you a secret message, figure out how to decrypt it and announce the result. You may need to use the Diffie-Hellman Tools and the Text to Integer converter.

Here’s another exponent problem to practice on. Try to compute $13^{453^{2022}}$ modulo $100$. For multiplying two digit numbers, you can use a calculator. 🙂

If time remains, try to break someone else’s message that wasn’t directed to you!

Write me a paragraph “check-in”; how do you feel the class is going? What are challenges, what can I do to help with those?

Compare your last daily post solutions with my solutions. Make sure you understand your errors or incomplete questions (if any). Ask me if you have questions, I’m easy to find on discord.

Use Euler’s And Fermat’s Little theorems (and maybe successive squaring or double-and-add/square-and-multiply) to compute $59^{(7^{115})} \pmod{26}$ by hand.

Use Euler’s Theorem to prove the following: Let $a \in (\mathbb{Z}/n\mathbb{Z})^*$ have multiplicative order $k$. Then $k$ divides $\varphi(n)$ (the Euler phi function of $n$). I will provide some hints on discord using the ‘spoiler’ feature.

Remember that you only need to spend 1 hour. If you get stuck on a problem, don’t spin your wheels; try some others instead and sleep on it. You can come back to things. I will post full solutions for these.

Compute the Euler phi functions $\varphi(12)$, $\varphi(26)$, $\varphi(27)$. For each of these $n$, verify your answer by computing the set $(\mathbb{Z}/n\mathbb{Z})^*$.

Another ciphertext exchange on discord!

Use Hill cipher to encrypt the answer to the question “What is your favourite vegetable?” You can use some Hill Cipher tools here, to avoid by-hand computations. Or you can write your own encryption/decryption program. You can choose your own (valid!) key.

Post your key and ciphertext. Use someone else’s key & ciphertext to get their plaintext and announce the result. There’s a #ciphertexts channel for this.

Can you find the Hill cipher key? The Hill cipher (with 2×2 matrices) was used to encrypt the plaintext SOLVED to get the ciphertext GEZXDS.

Consider Hill cipher with the matrix $$\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}$$ modulo $26$. Can you find two plaintexts that encrypt to the same ciphertext? (The plaintexts don’t need to be english, they can just be any letters.) What’s wrong with this matrix?

Prove that

if you take successive powers of $a$ mod $n$, i.e. $a,a^2,a^3,a^4,a^5,\cdots$, that eventually you will get a repeat (the same residue will appear more than once, e.g. $a^2$ might equal $a^7$)

if $a$ is invertible, then eventually you will get a $1$

Remind yourself how to use the Multiplicative Dynamics tools. Can you find an example where you never get a $1$ in that list?

A note about daily posts! Sometimes the tasks may take more than an hour, or be frustrating. Sometimes I give you tasks BEFORE I’ve taught you how to do them. (My philosophy is that that’s part of the exploratory, messy nature of effective mathematics learning.) In these circumstances, you should feel you have done your due diligence after one hour and hand in what you have (maybe skip over the frustrating task, at least at first). Then you can come back to them later sometime, as needed. For example, after Friday’s class, the Wednesday tasks should seem doable if they were not before, and you can go back to them to solidify understanding.

Quick review question: What is the inverse of 7 mod 11? What is the inverse of 7 mod 14? (Watch for trick questions!)

I’m assuming you know about binary, and how to write things in binary. If not, this PBS YouTube video gives a good review in the first four minutes. (The rest of the video is also relevant and interesting (about ASCII and unicode etc.) if you are curious.)

I’ve warned you several times that you cannot reduce an exponent modulo $n$ even when you are working in $\mathbb{Z}/n\mathbb{Z}$. So we might sometimes need to compute large exponents. Let’s suppose we need to compute $2^5$. We could start with $2$, and then:

multiply by $2$ to get $2^2=2 \times 2 =4$

multiply by $2$ to get $2^3=4 \times 2=8$

multiply by $2$ to get $2^4=8 \times 2=16$

multiply by $2$ to get $2^5=16 \times 2=32$

That’s four multiplications. Instead, we could do this:

multiply by $2$ to get $2^2=4$

now that we have $2^2=4$, we could multiply it by itself to get $2^4 = 4 \times 4 = 16$

multiply by $2$ to get $2^5 = 32$

That was only three multiplications! That’s more efficient. So, the challenge is to compute a high power by doing as few multiplications as possible.

Your challenge is to compute $2^{148}$ modulo $1000$. Imagine you have a calculator that will multiply two numbers modulo $1000$ for you (for example, you can use google, wolfram alpha or Sage on the course website), but WON’T just do big exponents. (Remember, it’s always efficient to reduce mod n between each multiplication, so you never get more than 3 digit numbers to work with.) How can you do this with the fewest multiplications possible? Try to do the best you can, and count the multiplications you use.

Use the double-and-add algorithm of the video (by writing 148 in binary) to demonstrate an efficient way to compute $2^{148}$.

What you just learned is what computers do, when implementing cryptosystems in modular arithmetic.

Now read Section 3.5 “Modular Exponentiation” of your textbook for another, different approach. Now work out this method for $2^{148}$? Better or worse? This is an easier algorithm to internalize and remember for use on a test.

Time left? I wouldn’t want you to get bored. If you still have some time left, you can optionally try to create a nice implementation of the double-and-add algorithm in your favourite language. I’d be happy to see that in the canvas inbox if you do. If you are new to programming, implementing the simpler algorithm of just multiplying by 2 repeatedly using a for-loop is a good first challenge. There are tons of “learn python” resources online; here’s a YouTube playlist that seems popular. Reach out to me!

Make sure you understand the ins and outs of the course setup (you’ve read all the top bar info on this site, heard me discuss in class, and have asked any questions if you have some), and have the textbook.

Please make sure you have set a nickname/alias in discord that is your first name with last initial or last name. Discord is meant to be a continuance of class, so we build community (so we like to know who is who).

Take a look at the multiplication table modulo $26$, and figure out when a function $\alpha x+\beta \pmod{26}$ is suitable for encryption (this is affine cipher). In other words, for which pairs $(\alpha,\beta)$ is the function $f(x)=\alpha x+\beta \pmod{26}$ invertible? Write out a complete answer (some way of describing which pairs work and which don’t). (If needed, remind yourself about invertible, bijective, injective, surjective.)

Come up with a short (one word is best) answer to the question “What’s the coolest math?” This is your plaintext.

Choose a pair $(\alpha,\beta) \in (\mathbb{Z}/26\mathbb{Z})^2$ to use as a key. Make sure you choice is suitable as described above.

Encrypt the plaintext with affine cipher (by hand, using the cryptography tools sheet if you like). If you need some notes on affine cipher, it’s Section 2.2 in the text. This gives you your ciphertext.

Post your ciphertext on the discord channel #ciphertexts, along with the key.

Choose the most recent user’s post (besides yours) from #ciphertexts, and decrypt it (by hand). Post the answer in the form “So-and-so thinks the coolest math is….”

Suppose you eavesdrop on your little sister’s communications, and she is using affine cipher. Her ciphertext is CRWWZ. You know she starts every message she writes with “HA” (she’s weird that way). Decrypt the message. Explain how you did it.

Write a proof for the Main Theorem of modular arithmetic that we did in class today (here are the lecture notes). This theorem can be found everywhere (including in your textbook), but try to write your own proof first. If you can’t, then look at a proof to understand the idea and then try to write your own with notes closed.

Check out this tool for drawing pictures of the function $f(x)=ax \pmod{n}$. Try it for $n=5$ and $n=6$ with different $a$’s.

Form a conjecture about which values of $a$ result in the function $f(x)=ax$ being invertible modulo n. You might want to try different $n$’s.

What do you think is the essential reason that $f(x)=3x$ is not invertible modulo $6$?

OPTIONAL: If you would like a longer discussion of how and why modular arithmetic is a well-defined mathematical system, and all the formal mathematics underlying it, then I’ve got a video for you (17:26). But watching it is optional; in this course we focus on the intuition, properties and applications, not the mathematical formalism in terms of equivalence relations.

Get yourself set up on discord. Before you use the invite link available in canvas, make sure your username is not offensive (I get a notification the moment you click the link). Discord has channels where you can chat with each other, and message are public by default. It also have a video/voice channel capability. Please choose an alias on our server that is your first name and last initial or first name and last name (let me know of any concern).

Read carefully through each of the pages that is listed on the TOP menu bar of this website (History, Notes/Videos, About, etc.). These constitute the syllabus for the course.

Make sure you have the textbook (Wade Trappe, Lawrence C. Washington, Introduction to Cryptography with Coding Theory, 2nd or 3rd edition). The third edition seems only available electronically. The editions are very similar and either one is fine.

Note: the next activity is to watch a video and do an accompanying worksheet. I strongly suggest working on this in groups, and collaborating on daily tasks with classmates in general. To that end, I’ve set two designated times to meet on discord to do the video with peers (totally optional):

Monday August 22nd at 9 pm

Tuesday August 23rd at 6 pm

The main activity for this daily post is to watch my video “Modular Arithmetic: User’s Manual” (9:22 mins:secs) and do the accompanying self-check worksheet. Please be sure to show your work on the last problem. (Note: you don’t need to print; you can work on a separate sheet of paper if desired.)

You will track your work on daily posts using this evaluation form. You’ll keep this all semester –you might want to print it out and clip it to your wall. Give yourself a score for your work today. You can always find the link to this file under “Notes/Videos” on the top bar.

After each daily post, there are two things for you to do: first, update your daily evaluation worksheet (the bullet point above), and then second, upload a record of your work to canvas. (There’s only one upload box on canvas, which you will use over and over again.) The record of your daily post activity should be ONE file including images/copy of your written work, and including a copy of your self-evaluation sheet as it stands currently (both sides). This is so we have a record we can return to if anything gets lost (chances are non-trivial that some student will lose their sheet at some point). If you’re having trouble making one file out of a bunch of images, one basic way that works is to put them into a google doc or word file and then print to pdf.

I’m flexible about it as you get used to this “daily task” system. Just try it out and let me know if there are any hiccups. I’m here to answer questions.