\Question{Squared RSA}
\begin{Parts}
\Part (5 points) Prove the identity $a^{p(p - 1)} \equiv 1 \pmod{p^2}$, where $a$ is coprime to $p$, and $p$ is prime. (Hint: Try to mimic the proof of Fermat's Little Theorem from the notes.)
\Part (10 points) Now consider the RSA scheme: the public key is $(N = p^2 q^2, e)$ for primes $p$ and $q$, with $e$ relatively prime to $p(p-1)q(q-1)$. The private key is $d = e^{-1} \pmod{p(p-1)q(q-1)}$.
Prove that the scheme is correct for $x$ relatively prime to both $p$ and $q$, i.e.\ $x^{ed} \equiv x \pmod{N}$.
%\Part Prove that this scheme is at least as hard to break as normal RSA; that is, prove that if this scheme can be broken, normal RSA can be as well. We consider RSA to be broken if knowing $pq$ allows you to deduce $(p - 1)(q - 1)$. We consider squared RSA to be broken if knowing $p^2q^2$ allows you to deduce $p(p - 1)q(q - 1)$.
\end{Parts}
\Question{Breaking RSA (15 points)}
%\begin{Parts}
Eve is not convinced she needs to factor $N = pq$ in order to break
RSA.
She argues: "All I need to know is $(p-1)(q-1)$... then I can find $d$
as the inverse of $e$ mod $(p-1)(q-1)$. This should be easier than
factoring $N$."
Prove Eve wrong, by showing that if she knows $(p-1)(q-1)$,
she can easily factor $N$ (thus showing finding $(p-1)(q-1)$ is at least
as hard as factoring $N$). Assume Eve has a friend Wolfram, who can easily return the
roots of polynomials over $\R$ (this is, in fact, easy).
% \Part When working with RSA, it is not uncommon to use $e=3$ in the public
% key. Suppose that Alice has sent Bob, Carol, and Dorothy the same
% message indicating the time she is having her birthday party. Eve, who is
% not invited, wants to decrypt the message and show up to the
% party.
% Bob, Carol, and Dorothy have public keys $(N_1, e_1), (N_2, e_2), (N_3,
% e_3)$ respectively, where $e_1=e_2=e_3=3$. Furthermore assume that $N_1,N_2,N_3$ are
% all different. Alice has chosen a number $0\leq x< \min\{N_1,N_2,N_3\}$ which
% indicates the time her party starts and has encoded it via the three
% public keys and sent it to her three friends. Eve has been able to
% obtain the three encoded messages. Prove that Eve can figure out $x$.
% First solve the problem when two of $N_1,N_2,N_3$ have a
% common factor. Then solve it when no two of them have a common factor.
% Again, assume Eve is friends with Wolfram as above.
%
%
% \textit{Hint}: The concept behind this problem is the Chinese Remainder Theorem:
% Suppose $n_1, ...,n_k$ are positive integers, that are pairwise co-prime.
% Then, for any given sequence of integers $a_1, ..., a_k$, there exists an
% integer $x$ solving the following system of simultaneous congruences:
% \begin{align*}
% x &\equiv a_1 \pmod{n_1} \\
% x &\equiv a_2 \pmod{n_2} \\
% &\vdots \\
% x &\equiv a_k \pmod{n_k}
% \end{align*}
% Furthermore, all solutions $x$ of the system are congruent modulo
% the product, $N=n_1 \dotsm n_k$. Hence:
% $x \equiv y \pmod{n_i} \text{ for } 1 \leq i \leq k \iff
% x \equiv y \pmod N $.
%\end{Parts}
\Question{Polynomial Practice}
\begin{Parts}
\Part If $f$ and $g$ are non-zero real polynomials, how many roots do the following
polynomials have at least? How many can they have at most?
(Your answer may depend on the degrees of $f$ and $g$.)
\begin{enumerate}[(i)]
\item (2 points) $f + g$
\item (2 points) $f\cdot g$
\item (2 points) $f/g$, assuming that $f/g$ is a polynomial
\end{enumerate}
\Part Now let $f$ and $g$ be polynomials over $\mathrm{GF}(p)$.
\begin{enumerate}[(i)]
\item (3 points) We say a polynomial $f = 0$ if $$\forall x, f(x) = 0$$.
If $f\cdot g = 0$, is it true that either $f=0$ or $g=0$?
\item (3 points) If $\deg{f} \geq p$, show that there exists a polynomial $h$ with
$\deg{h} < p$ such that $f(x) = h(x)$ for all $x \in \{0,1,...,p-1\}$.
\item (3 points) How many $f$ of degree \textit{exactly} $d 0$.]\\
(Hint: Try to relate it to something we know that's countable, such as $\Q \times \Q$)
\nosolspace{2cm}
\Part (5 points) Is a set of circles in $\R^2$ such that no two circles overlap necessarily countable or possibly uncountable? [\textit{Hint}: A circle is a subset of the plane of the form $\{(x, y) \in \R^2 : (x - x_0)^2 + (y - y_0)^2 = r^2\}$ for some $x_0, y_0, r \in \R$, $r > 0$. The difference between a circle and a disk is that a disk contains all of the points in its interior, whereas a circle does not.]
\nosolspace{2cm}
\end{Parts}