DUE Friday, September 11th, 2026

September 9, 2026 profstange

Relevant Textbook Sections:

2.4.4–2.4.5 (The theorems of Euler and Fermat; Using Euler’s $\varphi$ function), 2.7 (Runtimes and Big-Oh notation), 2.8–2.9 (The Discrete Logarithm and the Discrete Logarithm Problem), 2.10 (Parity of discrete log), 2.10.1 (The Baby-Step Giant-Step Algorithm)

To Do:

Reminder: the first test is in class on Wednesday, September 16th, 2026 (Module 1). See the Tests page for the syllabus.
Solutions to the last daily post (the big-oh comparisons and the baby-step giant-step computation) are now posted: Solutions to Daily Due Sep 9. All daily post solutions are collected on the Archive page.
A bit of math practice that shows that the parity (even or oddness) of the discrete log can be discovered easily. Let $p$ $p$ be an odd prime number.
1. Show that if $ab \equiv 0 \pmod p$ then $a \equiv 0 \pmod p$ or $b \equiv 0 \pmod p$ .
2. 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$ .
3. Let $g$ be a primitive root mod $p$ . Show that $g^{(p-1)/2} \equiv -1 \pmod p$ . (This uses the previous part.)
4. 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.
5. 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.
6. Check whether you are correct by finding $x$ (by any method).
7. Comment on the runtime of this test for the parity of $x$ .
8. Comment on whether parity of a discrete log is well-defined modulo $n$ . Why is it ok for odd primes $p$ ?
Review for Test 1. Use the Baby-Step-Giant-Step algorithm to solve the discrete logarithm problem $51 = 2^x \pmod{83}$ . ( $2$ is a primitive root modulo $83$ .) Present both lists, labelled so it is clear where each entry comes from, identify the collision, and explain how it gives $x$ . Then check your answer. You may use the tools on the Baby-Step Giant-Step page or the Sage Sandbox to generate the lists. Or do some by hand, for practice!
Review for Test 1. Compute $2^{(3^{2026})} \pmod{33}$ “by hand” (calculator is ok for multiplications and reductions, but show all steps). Remember to check the coprimality conditions that Euler’s theorem needs, each time you use it.
A runtime analysis. Here is a search problem: the input is two integers $N$ $N$ and $t$ $t$ . The goal is to decide whether $t$ $t$ appears in the list $1^3+1, 2^3+2, 3^3+3, \ldots, i^3+i, \ldots, N^3 + N$ $1^{3} + 1, 2^{3} + 2, 3^{3} + 3, \dots, i^{3} + i, \dots, N^{3} + N$ . Two algorithms: Linear search computes the list from the beginning, comparing each computed entry to $t$ $t$ , and stops when it finds $t$ $t$ or passes it. Binary search computes the middle entry, compares $t$ $t$ to that middle entry, discards the half of the list which cannot contain $t$ $t$ , and repeats on the half that remains, until it finds $t$ $t$ or runs out of list.
1. Determine the size of the input to this problem (in bits), as a function of $N$ .
2. Determine the runtime of each algorithm, in big-oh notation, as a function of the input size. Count a comparison of two integers as costing a number of bit operations proportional to their length in bits.
Remember to upload to canvas!

DUE Wednesday, September 9th, 2026

September 4, 2026 profstange

Relevant Textbook Sections:

2.7 (Runtimes and Big-Oh notation), 2.8–2.9 (The Discrete Logarithm and the Discrete Logarithm Problem), 2.10.1 (The Baby-Step Giant-Step Algorithm)

To Do:

Reminder: the first test is in class on Wednesday, September 16th, 2026 (Module 1). See the Tests page for the syllabus.
Solutions to the last daily post (a complete worked example of the Diffie-Hellman exercise, with numbers you can try in the tools) are now posted: Solutions to Daily Due Sep 4. All daily post solutions are collected on the Archive page.
For each of the following pairs of functions, determine if $f=O(g)$ $f = O (g)$ and if $g=O(f)$ $g = O (f)$ .
1. $f(x) =|\sin(x)|$ and $g(x) = 1/2$ .
2. $f(x) = 2^x$ and $g(x) = 3^x$ .
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 Baby-Step Giant-Step 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.
If you are so inclined, try to break one of the ciphertexts on discord from our Diffie-Hellman Key Exchange.
Remember to upload to canvas!

Added Sept 9: solutions to this daily post (the big-oh comparisons and the baby-step giant-step computation) are now posted: Solutions to Daily Due Sep 9.

DUE Friday, September 4th, 2026

September 2, 2026 profstange

Relevant Textbook Sections:

2.4.7 (Summary of Multiplicative Structure in the unit group), 2.5 (Diffie-Hellman Key Exchange)

To Do:

Added Sept 4: solutions to this daily post (a complete worked example of the exchange, with all the numbers) are now posted: Solutions to Daily Due Sep 4.

Notice: the first test will be in class on Wednesday, September 16th, 2026 (Module 1). See the Tests page for the syllabus.
Solutions to the last two daily posts are now posted: Solutions to Daily Due Aug 31 and Solutions to Daily Due Sep 2. Check your work against them. All daily post solutions are collected on the Archive page.
Watch the video “Diffie-Hellman Key Exchange Exercise” (~16 min) [ link here ], which is a tutorial to accompany the following exercise. In the video, I demonstrate how to use the course website tools (on this website) to put your Diffie-Hellman public key up on the discord server, and send a message to someone there. Here are the written notes from that video.
Here are the full written instructions: you will perform a Diffie-Hellman Key Exchange in order to send a message to someone. 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):
1. Create a secret message which is at most 6 characters long. It should answer “Why CU?” Please don’t make it longer or this exercise won’t work.
2. 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.)
3. 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.
4. Use the Diffie-Hellman Tools (second box) to find a random secret $a$ . We’ll call this your secret key. Keep it secret and SAVE IT, 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.)
5. Compute $g^a$ using the Diffie-Hellman Tools third box appropriately (no need to do this by hand!) We’ll call this your public key.
6. Announce your public key on discord #public-keys. Be sure to explain this is your “Diffie-Hellman Public Key” (there will be other types later).
7. Find someone else’s public key ( $g^b$ ) on discord (the most recent public key on the #public-keys channel is best, so everyone gets to have part of the fun). 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).
8. Add the shared secret to your message mod $p$ . Announce the result on discord in the #ciphertexts channel as the secret message for Bob. They can find your public key on the #public-keys channel. Your post might look like “My Diffie-Hellman message for @soandso is X.”
9. When someone sends you a secret message, figure out how to decrypt it and announce the result (so you can check it worked!). You may need to use the Diffie-Hellman Tools and the Text to Integer converter.
Remember to upload to canvas!

DUE Wednesday, September 2nd, 2026

August 31, 2026 profstange

Relevant Sections of Textbook

2.2.9 (Invertibility)
2.2.10 (unit group)
2.4 (Multiplicative dynamics)

To Do:

Added Sept 2: solutions to the daily due Aug 31 are now posted: Solutions to Daily Due Aug 31.

In class, we proposed a formula $\varphi(n) = n(1 - 1/p_1)(1-1/p_2)\cdots(1-1/p_s)$ when $n$ is a product of distinct primes $p_i$ . Verify this for $n = 15$ and $n=30$ by comparing to your computations of $\varphi$ from the last daily post.
Write me a few sentences “check-in”; how do you feel the class is going? What are challenges, what can I do to help with those?
Use successive squaring to compute $3^{133} \pmod{1009}$ . You can use a calculator for the multiplications/reductions, but show all steps of the algorithm. If you learned about double-and-add (see last daily post), you can use that if you prefer.
Some fun modular arithmetic, part one:
1. Verify that $7$ is coprime to $12$ (factor them both).
2. Compute $\varphi(12)$ .
3. Explain what Euler’s theorem says about powers of $7$ modulo $12$ . Why did we check the last two things?
4. Compute $7^{115} \pmod{12}$ by hand using Euler’s Theorem. Calculator is ok for multiplications and reductions, but show all steps.
Some fun modular arithmetic, part two:
1. Verify that $59$ is coprime to $26$ (factor them both).
2. Compute $\varphi(26)$ (it’s important you get this right, check your answer with the Sage Sandbox (the euler_phi function is listed there)).
3. Compute $59^{(7^{115})} \pmod{26}$ by hand (this may use the previous problem…)
Use what you learned from the last few problems to compute $3^{(11^{200006})} \pmod{50}$ “by hand” (this will always mean calculator is ok for multiplications and reductions, but show steps).
Observe (verify) that $\varphi(15) = 8$ and $3^8 = 6 \pmod{15}$ . (You can check these on Sage or by hand or both.) This looks like it contradicts Euler’s Theorem. Why is it ok?
Remember to upload to canvas!

DUE Monday, August 31st, 2026

August 28, 2026 profstange

To Do:

Solutions to the last daily post (the one due today) are now posted: Solutions to Daily Due Aug 28. Check your work against them. All daily post solutions are also collected on the Archive page.
Quick review question: What is the inverse of 7 mod 11? What is the inverse of 7 mod 14? (Watch for trick questions!)
For each of the following $n$ , compute the set $(\mathbb{Z}/n\mathbb{Z})^*$ and therefore its cardinality $\varphi(n)$ : $n=12$ , $15$ , $16$ , $26$ , $27$ , $30$ .
Practice and reasoning with modular arithmetic with a cryptography flavour. If the affine cipher key $(\alpha, \beta)$ is ‘badly chosen’ (i.e. $\alpha$ may not be invertible), then bad things can happen. Find an example where two different plaintexts encrypt to the same ciphertext. (The plaintexts don’t need to be english, they can just be any letters.)
Some abstract thinking about modular arithmetic. Prove (explain your reasoning) that:
1. 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$ ). (Hint: finiteness)
2. If $a$ is invertible, then some power of $a$ is $1$ . (Hint: use the first part somehow.)
3. Can you find an example residue $a$ modulo $n$ for some $a$ and $n$ where no power of $a$ is ever $1$ ? You might want to mess around with the various Sage tools on this site.
Practice with modular arithmetic in the context of matrices, with a cryptography flavour.
1. The Hill cipher (with 2×2 matrices) was used to encrypt the plaintext SOLVED to get the ciphertext GEZXDS. (Two letters were encrypted at a time.) Can you find the Hill cipher key?
2. 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 (why isn’t encryption injective?)?
If it sounds fun, learn a useful new algorithm! The Double-And-Add algorithm allows for fast exponentiation, among other things; it’s a sort of refinement of successive squaring.
1. First, watch this video (6:09) which gives a general algorithm.
2. Use the double-and-add algorithm of the video (by writing 148 in binary) to demonstrate an efficient way to compute $2^{148}$ .
3. Program it if you feel like it.
Remember to upload to canvas!

DUE Friday, August 28th, 2026

August 26, 2026 profstange

To Do:

Solutions to the last daily post (the one due today) are now posted: Solutions to Daily Due Aug 26. Check your work against them. All daily post solutions are also collected on the Archive page (when I’m on top of things!).
CIPHERTEXT CHAIN! This time with affine cipher.
1. Come up with a short (one word) answer to the question “What’s the coolest math?” This is your plaintext.
2. Choose a key $(\alpha,\beta) \in (\mathbb{Z}/26\mathbb{Z})^2$ . Make sure your choice is suitable as a key, as we discussed in class.
3. Encrypt the plaintext with affine cipher (by hand, using the cryptography tools sheet if you like). This gives you your ciphertext.
4. Post your ciphertext on the discord channel #ciphertexts, along with the key.
5. Choose the most recent user’s post (besides yours) from #ciphertexts, and decrypt it (by hand).
6. Post the answer in the form “So-and-so thinks the coolest math is…”. Use discord’s “spoiler” feature to hide your answer, in case other students want to practice, or end up using the same ciphertext (this never works quite perfectly).
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.
Find the inverse (if it exists) of: $2 \pmod{17}$ , $8 \pmod{11}$ and $3 \pmod{15}$ . If it doesn’t exist, explain why.
Come up with the fastest way to compute $3^{519}$ modulo $11$ by hand. That is, count the multiplications you need to do in your full solutions (you can’t use secret knowledge about mod 11 for example, you have to compute anything you plan to use), and try to minimize that number by being clever about your method. It should be doable by hand (i.e., don’t do 500+ multiplications!!) Post the number of multiplications you have to do (but not your secret sauce) in the #daily-collaboration channel, as a sort of friendly competition.
Remember to upload to canvas!

DUE Wednesday, August 26th, 2026

August 24, 2026 profstange

To Do:

Please check the previous daily post (scroll down) and take care of the missing administrative items you haven’t done.
Please make sure you are now fully aware of the way daily posts work (you set aside an hour; you upload evidence of your worktime). We will have discussed this in class.
The main activity for this daily post is to watch my video “Modular Arithmetic: User’s Manual” (9:22 mins:secs; link above requires CU access, no ads; also on YouTube here), 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; in general this type of thing is true, since you are just showing evidence of your work, I’m not picky.)
Explain how XOR can be described in terms of modular arithmetic.
For the course, we will use Sage Mathematics Software for computations. Here’s a Sage worksheet that shows how to use Sage as a calculator for modular arithmetic. Check it out (do each computation by hand (except the last three, which we haven’t discussed yet, concerning inverses/dividing) and then compare to the computer output). Note: worksheets on the course website do not save your data.
Create an example modulo 10 of residues $a,b,c$ such that $a \not\equiv b \pmod{10}$ and $c \not\equiv 0 \pmod{10}$ , but $ac \equiv bc \pmod{10}$ . Explain why this means you “can’t always cancel in modular arithmetic.”
Compute $10^{12} \pmod{11}$ by cleverness. Check your answer with Sage. Verify that $10 \not\equiv 10^{12} \pmod{11}$ . Explain why this shows you “can’t take mod up in the exponent”.
Catch up on the last daily post (classical ciphers), if needed. While you’re doing this, think about how each of them can be described in terms of modular arithmetic. You can check your decryptions against the Solutions to Daily Due Aug 24 (AI generated) (problems 9–12).
Upload a record of your work today to canvas (as always).

DUE Monday, August 24th, 2026

August 21, 2026 profstange

Today’s tasks are mostly reading and learning by reading. As you read the textbook, you will find exercises scattered through the text. Part of reading the text for full understanding is doing these exercises until you are very confident in your understanding.

Please read the full list of tasks before you begin. The final task (uploading to canvas) should happen even if you don’t finish everything else.

To Do:

Log into canvas and follow the instructions to get set up on Discord, which we will use during the semester.
Log into canvas and fill out the video waiver (I record my screencast during lectures for future students).
Log into canvas and fill out the AI questionnaire (I’d like to know your AI opinions).
Print out the Self-Eval Sheet, or save a copy you can edit on your device. You will fill this out each time you do your daily post work. It should be self-explanatory (read the instructions!).
Read the pages which have tabs across the top of this website (About, Archive, Notes/Videos, …) so you know how the course is run. This is the syllabus and I won’t use class time to go over it. This is important.
Go to the Textbook link (top left on this site) and view the textbook. If you would like to use the (experimental) AI overlay, you have to enter the code that I sent you in canvas mail, which has a $5 starting budget (AI costs money). Once you put that in, it is stored as a cookie. Then you can simply highlight a passage of interest with your mouse, and you will find different options, like “show me an example” or “chat”. Note: there is no expectation of privacy. Whatever you find useful, you can save as a margin note, and then it is viewable to everyone who uses the textbook. (I moderate these.) If you don’t want the AI overlay, you use it in “Static Mode” and it’s a traditional (human-written by me!) textbook with built-in interactives.
READ Chapter 1 of our text, up to the end of Section 1.3 (including Enigma machine), doing the exercises. Your goal is to understand how each of these old ciphers works, so that you can encrypt and decrypt by hand. And to have a bit of a historical viewpoint.
CIPHERTEXT CHAIN! Encrypt a message (a quote you like), using a cipher of your choice (tools are in the textbook as interactives) and post it to the Discord #ciphertexts channel. Choose the ciphertext posted by the last person on that channel, to try to decrypt. Try to guess which cipher it was encrypted with, before you try to decrypt. Feel free to report out how you decrypted (by hand, using the provided tools, whether you guessed right…). This is for fun and to get used to discord and each other. Don’t sweat it.
Decrypt the following Vigenère cipher by hand, showing work, using the key “CRYPTO”: geagrdvzmc
Decrypt the following Caesar cipher by hand, showing work, using the key “D” (that is, A becomes D): hw wx euxwh
Decrypt the following ADFGVX cipher by hand, showing work, using the Polybius square shown in the textbook and column order 1324: VDDGXDXVGGAXAAAA (Hint: we didn’t really talk about decryption, so you’ll have to figure out how to reverse engineer it! Explain your ideas!)
Decrypt the following one-time pad message (in binary) by hand, using key “001101”: 100100
At the end of each daily post, collect evidence of your work, including your self-eval sheet, and upload it (PDF, jpg, etc.) to the appropriate Daily Post dropbox in Canvas. This is not graded. But it is our joint record of your hard work throughout semester. This is important.

Welcome to Cryptography! (Fall 2026)

August 20, 2026 profstange

Hello class and welcome!

I’m your professor, Dr. Katherine Stange. A little about me. My job as a professor is half teaching and half research. My research is in number theory and cryptography, so I especially enjoy this course. When I’m not working, I like to cycle up Flagstaff, or anywhere that is uphill.

I hope you’re going to find this class challenging but fun and exciting. This class has some features I want to make sure you are aware of up front:

The focus on the course is on the mathematical algorithms underpinning modern cryptography and cryptanalysis, mostly public-key cryptography, as well as some coding theory. We will tie the algorithms we study to real-world implementations and events. Topics will include basic number theory including elliptic curves and finite fields, current public-key cryptosystems, basic quantum computing and quantum cryptography, post-quantum (quantum-safe) cryptography, and coding theory.
This is a mathematics course, and you will be expected to reason mathematically about mathematical objects, follow and understand proofs, know definitions, be able to reason out examples, predict the outputs of algorithms and computations, etc. However, this course will not emphasize proof-writing. You certainly do not need to be a math major, but you need to have some mathematical/analytical thinking skills. There are few explicit mathematical pre-requisites, but linear algebra will help a lot.
I will teach and expect some basic python programming, so we can implement algorithms. This will be modular, so if you have coding skills already, you won’t need to “redo” your basic skills.
I expect you to find 1 hr between each class for homework. There will be “daily posts”: per lecture assignments. The rest of your study time will be discretionary and flexible.
Assessment is in-class. Homework is self-reported and solutions posted; it is not graded. Your understanding is assessed through in-class tests.
We will use discord. Please plan to check discord and this website regularly for updates. Things move fast.
There will be a poster project in small groups. This is a self-guided research project into a related topic in the course.
Students taking 5440 (instead of 4440) will replace the poster project with more extensive individual projects.

To Do:

To learn all about the course, examine the tabs in the header menu. These tabs together form the syllabus.
Log into canvas for access to the discord sign up link.

Relevant Textbook Sections:

To Do:

Relevant Textbook Sections:

To Do:

Relevant Textbook Sections:

To Do:

Relevant Sections of Textbook

To Do:

To Do:

To Do:

To Do:

To Do:

Hello class and welcome!

To Do:

Fall 2026 – Professor Katherine Stange