Tests were returned in class. I forgot to print the solutions, so they are on canvas. Please compare the solutions to your test and figure out what went wrong.

Retakes: You may retake one of the 10 point problems in Part B that you attempted. The written retakes will be posted on canvas (for both Module 2 and 3) as soon as I can manage.

If you got 6 or higher on your retake problem, you will do a written replacement problem.

If you got 5 or lower, you can schedule to meet in person for a retake. If you want to do this, please email me.

What are the units of $\mathbb{F}_7[x]$? (This is a concept check kind of question.)

Do two polynomial long divisions:

In $\mathbb{F}_2[x]$, divide $x^4 + x + 1$ by $x^2 + x + 1$.

In $\mathbb{F}_5[x]$, divide $x^5 + 3$ by $x^2 + 2$.

Determine whether $x^2 + x + 1$ is irreducible in $\mathbb{F}_3[x]$. (This may require an exhaustive search method; you may use Sage if you like, but it’s not that bad by hand if you are efficient/thoughtful on the method.) What about $x^2 + 2x + 1$?

Working in $\mathbb{F}_3[x]$, do the Euclidean algorithm on $x^4+x^3 + x^2 + 2x + 1$ and $x^2 + 2$. What is the gcd?

Challenge: can you build a finite field with 8 elements?

Please ensure you upload a current version of your self-assessment document for daily posts.

For those of you who are still waiting on a paper re-do for the first assessment, we will do it in combination with the second assessment, so keep waiting a couple more days.

Let us consider polynomials in $x$ with coefficients in $\mathbb{Z}/3\mathbb{Z}$. For example, $x + 2x \equiv 0$ and $2x^2 + 2x^2 \equiv x^2$.

Add $2x+2$ to $x^2 + 2x+1$. The result should have coefficients chosen from $0, 1, 2$.

Multiply $x+2$ and $x+1$. The result should have coefficients chosen from $0, 1, 2$.

Recall that we defined $\mathbb{Z}/n\mathbb{Z}$ as the set of integers with the additional “rule” that $n\equiv 0$ so we can remove multiples of $n$. In the same way, consider the set of polynomials in the variable $x$ with coefficients in $\mathbb{Z}/3\mathbb{Z}$ (as in the last question), but “modulo” $x^2+1$. In other words, whenever we see an $x^2+1$, we can remove it. (Hint: this also means whenever we see an $x^2$, we can replace it with $-1 \equiv 2$). For example, $(x+1)(x+1) \equiv x^2 + 2x + 1 \equiv 2+ 2x + 1 \equiv 2x $.

Multiply out and simplify $(x+1)x$.

Multiply out and simplify $(x+1)(x+2)$.

Check your answer against my answer on the #daily-collaboration channel of discord. If things aren’t working, ask for help on discord from me or your peers.

We have defined a new “ring” (number system)! This ring is finite. Write out a list of all of its finitely many elements.

Write out an addition table for these elements.

Write out a multiplication table for these elements.

On the #daily-collaboration channel of discord, put up a flashcard quiz question: that is, give a problem (to add or multiply two elements) and then put its answer as a spoiler (surrounded by double bars), so someone else can use their addition/multiplication tables to check their answer to your quiz question.

Use your tables to check someone else’s quiz question. In this way, we will probably/hopefully quickly diagnose any problems with the computations and work out the bugs so everyone is getting good at it!

If you make an error in your quiz question, you can use the discord edit functionality to fix it. Eventually we’ll have a bunch of great quiz questions up there to check your work against!

You have a module assessment in class; see previous posts for some info; the Goals page is all updated with topics and review questions. I’ll try to be on discord for questions.

You can use a calculator (not a phone, tablet or computer).

Don’t forget there is a MODULE 3 assessment on Monday. See “Goals” where I’m marking the relevant material in red. See the last daily post for some more details.

I’m having office hours Wed 2 pm (Oct 5) and Fri 9 am (Oct 7) in my office at Math 308. I’m also available on discord over the weekend as much as I can manage.

In particular, check if you received any messages from the RSA ciphertext chain and announce their decryption (many messages didn’t get checked yet).

You will sign a document on the #ciphertexts channel.

For your message, write your name — a short form of it at most 6 letters. Turn this into a number in the usual way.

Use the public, private RSA key pair you created for the RSA ciphertext chain previously. (If you lost it, you’ll have to make another, but it’s better to use your old keys. One of the things about public key cryptography is not losing your keys.)

Create an RSA signature for the message using your keys. Announce this on the #ciphertexts channel (you should announce the message, the signature, and your public keys).

Now, find someone else’s signed message and verify that their signature is valid.

Check that the message they signed is their name.

Announce that you have validated a signature.

Please study for your module 3 assessment! Bug me on discord with questions.

THERE WILL BE MODULE 3 ASSESSMENT in-class on MONDAY OCTOBER 10. The format will be similar to the previous assessment. Not explicitly cumulative beyond the necessary; we will still need basic facility with modular arithmetic and facts like Fermat’s little theorem etc. that we continue to use. I will update the list of topics to show what we have covered since the last module with red checkmarks.

Compare the previous daily post to the solutions and learn from your mistakes.

Factor $n=199163$ using the quadratic sieve method demonstrated in class. (You will also find some notes on Overleaf and in your textbook in the Factoring section (Sec 6.4.1 in 2nd ed).) You can use the Quadratic Sieve Tools page to produce the relations you will need. Hint on discord (I indicate a useful factor base, in case you are getting bogged down by too many primes).

Suppose Eve listens in to an RSA session, so she knows Bob’s public key $(n,e)$ and the ciphertext $c$. Suppose she computes two lists: (a) a list of $c x^{-e} \pmod n$ for many small $x$; (b) a list of $y^e \pmod n$ for many small $y$.

Explain how she can compute the message if she finds a collision between these two lists.

How likely is a collision? What would have to be true about the message for a collision to happen?

Write out a proof (I just appealed to your intuition in class), that if $x^2 \equiv y^2 \pmod{n}$ and $x \not\equiv \pm y \pmod{n}$, then $\gcd(x+y,n)$ is a proper (non-trivial, not $1$ or $n$) factor of $n$.

True fact: $16080 = 127^2 – 7^2$. Without doing any factoring or computations besides a bit of adding and subtracting, factor $16080$ as a product of two integers. (Hint on discord if you are stuck.)

Demonstrate the p-1 factoring method on $n=5063$. Show the structure of the calculation, but you can use Sage for modular exponentiation, gcd’s, and division. (You can write a little Sage for-loop to do this, but write up the results in such a way that it demonstrates the method.)

Try to demonstrate the p-1 factoring method for $n=5963$. It won’t work… what goes wrong?

Why did the last example fail? Can you design another $n$ for which this method fails?

If you haven’t already, please send take the anonymous feedback form for the class (this is the same form linked on the last daily post).

If you didn’t complete the RSA ciphertext chain from last daily post, please catch up now (it’s an important one to get a handle on). Click back for instructions.

Use Fermat’s Primality Test to detect whether 2001 and 2003 are composite or probably prime. Show your work (but you can use a calculator like Sage for the exponentiation).

If one of them is probably prime, then try a different a and explain what you learn.

On the last daily post, you computed the square roots of $-1$ modulo $65$ using Sage. Now compute them by hand using the Chinese Remainder Theorem (example in class and in the overleaf). Make sure you get the same answers!

An RSA ciphertext chain! We will use the #ciphertexts channel.

If you need a review of RSA, check the lecture notes, overleaf (where there’s an explicit example with Sage advice), video and textbook (Section 6.1 in 2nd edition). For what follows, the Sage Sandbox page should be useful, as may be the RSA Tools page. These pages show how to do operations like modular inverse, exponentiation, and euler phi function in Sage. You can use Sage to do all your computations.

First, set up your public and private key. Choose two 8-decimal-digit primes and form their product $n$. Choose an encryption exponent $e$ that is positive and less than $\varphi(n)$. Reveal your public key $n$ and $e$ on the discord #ciphertexts channel. Compute your decryption exponent $d$ and keep it safe (along with $p$ and $q$) in a private file on your computer. This is your private key information.

Create a secret message which is at most 6 letters long. It should answer “What’s something awesome?” 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.)

Now find someone else who has posted their public key, and encrypt your message to that person. Post it on the #ciphertexts channel for them (use @theirname to alert them).

When someone posts a message for you, decrypt it and announce the result using discord’s “spoiler” feature (in case anyone else wants to compute the same plaintext).

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