Reminder: Test 2 (Module 2) is in class on Wednesday, October 7th.

Relevant Textbook Sections:

3.8.3 (The role of squares in factoring).

To Do:

1. Suppose $p \equiv 3 \pmod 4$ and $a$ is a square modulo $p$. The following observation gives a method to compute a square root of $a$. Explain why our setup implies $a^{(p-1)/2} \equiv 1$. Show that $x = a^{(p+1)/4}$ satisfies $x^2 \equiv a \pmod p$. Demonstrate the method with $p = 19$ and $a=6$. What goes wrong if you try the same formula for $p = 13$ and $a = 10$? (Note $6^2 \equiv 10 \pmod{13}$, so $10$ does have square roots.)
2. Suppose $n$ is a product of two primes which are $3 \mod 4$. Explain how, if you can factor $n$, you could find square roots modulo $n$ using the last exercise. (Hint: CRT.)
3. Find all four square roots of $71$ modulo $77 = 7 \cdot 11$. Hint: find the square roots modulo $7$ and modulo $11$ separately, then combine them with CRT.
4. Explain how, if you can find square roots modulo $n$, this allows you to factor $n$. (Find square roots means find all square roots.) Hint: this is just recalling something we’ve been discussing in class about square roots and factoring.
5. Just a note: There are also more complicated ways to find square roots modulo primes that are $1$ modulo $4$. So the exercises above show that factoring $n$ is considered equivalent to finding square roots modulo $n$.
6. Find the square root(s), if any, of $3$ modulo $11$ using the algorithm from the first example. Now draw the dynamical portrait of powers of $3$ modulo $11$. Label each vertex as $3^x = y$ for whatever $x$ and $y$, so each vertex can be interpreted as its value mod $p$ and its power of $3$. Can you use this diagram to explain why the method works?