Solve the system of linear equations $x \equiv 5 \pmod{11}$ and $x \equiv 8 \pmod{24}$. Use the method demonstrated in class.

In the following problem, try to find a method of determining an example, not just trial and error. Give an example of integers $m \neq n$ which are NOT coprime (so $\gcd(n,m) > 1$), and integers $a$ and $b$ so that the system of linear equations $x \equiv a \pmod m$, $x \equiv b \pmod n$ has:

no solution

more than one solution (a different $a$ and $b$ will be needed)

explain your method for finding your examples

This problem is about square roots.

How many square roots does -1 have in the real numbers?

How many square roots does -1 have in the complex numbers?

Using Sage, find all the square roots of $-1$ modulo $5$, modulo $7$, modulo $13$ and modulo $5 \cdot 13=65$. Hint: you can use a for loop and check for every residue $x$ whether $x^2$ comes out to $-1$, and print it out when it does. Screenshot your code to include in what you submit. The Sage Sandbox should be good enough for this (a few lines of code).

Do you think this is weird?

Can you find a modulus where $-1$ has more than 4 square roots?

If there’s time remaining, consider whether the following statement is true or false: $a$ is invertible modulo $nm$ if and only if $a$ is invertible modulo $n$ and invertible modulo $m$. Maybe it is true sometimes (for some types of pairs $n$ and $m$).

Find the inverse of 6 modulo 13 using the Euclidean algorithm.

If you know $x \equiv 3 \pmod{6}$, what do you know (if anything) about the following values (in other words, could they be anything, or are they restricted to one or a few possibilities)?

$x \pmod{3}$

$x \pmod{12}$

$x \pmod{5}$

The goal of this exercise is to work out the runtime of the Euclidean algorithm:

Think of the Euclidean algorithm as replacing one pair $(a,b)$ with a new pair $(a’,b’)=(b,a-qb)$ at each step. For example, if we start with $(a,b)=(183,105)$ as on the last daily post, then we get $(a’,b’)=(b,a-b)=(105,78)$ at the next step.

Show that, if $b < a/2$, then $b’ < a/2$.

Show that, if $b \ge a/2$, then $b’ \le a/2$.

Conclude that after two steps $(a,b) \rightarrow (a’,b’) \rightarrow (a^{”},b^{”})$, the size of the first entry has decreased by at least half (so, it may have decreased more than that).

BRING A LAPTOP TO CLASS, WE WILL DO A WORKSHOP DAY.

In class you received your Module 2 assessment back, along with solutions (on paper). Please compare your solutions to the published solutions and take time to understand all your (and my!) errors.

There is an opportunity to replace one grade from among the Part B questions (four questions each worth 10 points):

If you wish to replace a grade of 7, 8, or 9, I will provide a similar problem and ask you to hand in a solution on canvas. I will announce this after I have finished the in-person replacements for other students.

If you wish to replace a grade less than or equal to 6, then we will meet in person, and I will ask you to solve a similar problem. If you wish to do this, then please schedule a time with me (zoom or in person). This time can be anytime in the next week or so, but you must contact me to schedule it before Wednesday. Just email me to set this up.

Just some extra info. I have a very special place in my heart for the euclidean algorithm. I have written up my explanation from class in the overleaf course notes (available in “Notes/Videos” in the top bar). I also have two videos about it under “Notes/Videos” in the top bar. These videos explain the same algorithm, but not exactly the same (more “coats of paint” to your understanding) and you may wish to watch them for review at some point.

Compute gcd(183,105). Show the process by hand.

Solve the Diophantine equation (meaning, find all integer solutions, show the process by hand):

183x + 105y = 0

183x + 105y = 3

183x + 105y = 1

Looking at your work above, what is the gcd of 61 and 35 (it should not require new computations, it’s there for you to see)

Looking at your work above, what is the full set of solutions to $35x + 61y = 1$? (it should not require new computations, it’s there for you to see in your work above)

Find the inverse of 35 modulo 61. This should not require new computations either; it should be discernible from your work above. Hint: To find the inverse of $a$ modulo $n$, you need to solve $ax \equiv 1 \pmod n$, which is to say, $ax + ny = 1$.

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.