\documentstyle[11pt]{article}

\newcommand{\R}{{\sf R\hspace*{-0.9ex}\rule{0.15ex}{1.5ex}\hspace*{0.9ex}}}
\newcommand{\N}{{\sf N\hspace*{-1.0ex}\rule{0.15ex}{1.3ex}\hspace*{1.0ex}}}
\newcommand{\Q}{{\sf Q\hspace*{-1.1ex}\rule{0.15ex}{1.5ex}\hspace*{1.1ex}}}
\newcommand{\C}{{\sf C\hspace*{-0.9ex}\rule{0.15ex}{1.3ex}\hspace*{0.9ex}}}
       
\setlength{\topmargin}{-0.8in}
\setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.25in}
\pagestyle{empty}

\begin{document}

\noindent
{\large Design and Analysis of Algorithms \hfill Neal Young}

\noindent
{\large Computer Science 45 \hfill}

\noindent
{\large Due: in class Friday, May 2, 1997 \hfill}

\vspace{.3in}

{\LARGE 
\begin{center}
Problem Set 4
\end{center}}
\vspace{.2in}

\begin{enumerate}

\item

  Prove that gcd$(a,b)$
  is the smallest positive element of $\{ai + bj : i,j \in \N\}$.

  (See CLR problem 33.2-7.)

\item

  Given primes $p$ and $q$, integer $n=pq$,
  and integer $e$ relatively prime to $\phi(n)$,
  show how to efficiently compute
  $d \equiv e^{-1} \pmod{\phi(n)}$.

  What does this have to do with RSA?

\item Exercise 33.7-3 (random self-reducibility of RSA).

\item Exercise 33.8-2 (Carmichael numbers).
  
\end{enumerate}
\end{document}
