\documentclass{article}
\voffset=-0.05\textheight
\textheight=1.1\textheight
\hoffset=-0.05\textwidth
\textwidth=1.1\textwidth
\title{Math 480 (Spring 2007): Homework 4}
\author{\bf Due: Monday, April 23}
\date{}
\include{macros}

\begin{document}
\maketitle 

\noindent{\bf There are 5 problems.} Each problem is worth 6 points
and parts of multipart problems are worth equal amounts.  You may work
with other people and use a computer, unless otherwise stated.  Acknowledge
those who help you.\\

\begin{enumerate}

\item\label{ex:solnsqrtmod35} (Work by hand alone on this.) Find all {\em four} solutions
$x$ with $0\leq x < 55$ to the equation
$$
  x^2 - 1\con 0 \pmod{55}.
$$

\item (Work by hand alone on this.) How many solutions (with $0\leq x <15015$) are there
to the equation
$$
  x^2 - 1 \con \pmod{15015}.
$$
You may use that $15105 = 3\cdot 5 \cdot 7 \cdot 11 \cdot 13$.

\item Find the first prime $p>19$ such that the smallest primitive root
modulo $p$ is $19$.  (This requires a computer.)

\item\label{ex:crypto1}  You and Nikita wish to agree on a secret key using
the Diffie-Hellman key exchange.  Nikita announces that $p=3793$ and
$g=7$.  Nikita secretly chooses a number~$n<p$ and tells you
that $g^n\con 454\pmod{p}$.  You choose the random number 
$m=1208$.  What is the secret key?

\item In this problem you will digitally sign the number 2007. 
The grader will verify your digital signature. 
\begin{enumerate}
\item Choose primes $p$ and $q$ with $5$ digits each,
but do not write them down on your homework assignment.  Instead,
write down $n=pq$. (Your answer to this problem is $n$.  The grader
will factor $n$ using a computer and verify that indeed $n=pq$
with $p$,$q$ both prime.)
\item Let $e=3$.  Compute the decryption key $d$ such that
$ed\con 1\pmod{\vphi(n)}$.  Do not write down $d$.  Instead
encrypt the number $2007$ using $(d, n)$, i.e., digitally
sign $2007$.  Your answer is the number $m$ modulo $n$. 
(The grader will encrypt $m$ using your public key $(3,n)$;
if the grader gets $2007$ as the encryption, you get full
credit; otherwise no credit.)
\end{enumerate}
\end{enumerate}

\end{document}




%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: