\documentclass[11pt,fleqn]{article}
\usepackage{latexsym,epsf,epsfig}
\usepackage{amsmath,amsthm}
\begin{document}
\newcommand{\mbf}[1]{\mbox{{\bfseries #1}}}
\newcommand{\N}{\mbf{N}}
\renewcommand{\O}{\mbf{O}}
\newtheorem{thm}{Theorem}
\section*{CS 70 homework 7 solutions}
Your full name: PUT YOUR NAME HERE
\newline
Your login name: PUT YOUR LOGIN NAME HERE
\newline
Homework 5
\newline
Your section number: PUT YOUR SECTION NUMBER HERE
\newline
Your list of partners: LIST YOUR PARTNERS HERE
\newline
\begin{enumerate}
\item (Programming assignment. Please submit a file called
{\tt rsa.scm} or {\tt RSA.java}.)
\item
Suppose someone chose a value for $n$ that was not a product of two primes,
i.e., $n=pq$ with $p>1$, $q>1$, and $q$ is composite.
It would obviously be easier to factor, thus posing a security risk.
But would the encrypting and decrypting operations still work
with this $n$? Defend your answer.
YOUR ANSWER GOES HERE.
\item
Consider the following result, first proved many centuries ago.
\begin{thm}[Euclid]
There exist infinitely many primes.
\end{thm}
\begin{proof}
Assume to the contrary that there exist finitely many primes.
Let these primes (in increasing order) be
$p_1=2$, $p_2=3$, $p_3=5$, \ldots, $p_k$.
Let $q_k = p_1 p_2 p_3 \cdots p_k + 1$.
Note that $q_k$ is a new number not in the list of primes
$p_1,\dots,p_k$.
At the same time, it is not divisible by $p_i$ for any $i$,
since $q_k \equiv p_1 p_2 p_3 \cdots p_k + 1 \equiv 1 \pmod{p_i}$,
which would mean that $q_k$ is a new prime
different from $p_1,\dots,p_k$, which is a contradiction.
This completes the proof.
\end{proof}
Let $p_1,\dots,p_k$ represent the first $k$ primes.
\begin{enumerate}
\item
Are we guaranteed that $p_1 p_2 p_3 \cdots p_k + 1$ is always
prime for all $k \ge 1$?
Explain.
YOUR ANSWER GOES HERE.
\item
Is the above proof valid?
Explain.
YOUR ANSWER GOES HERE.
\end{enumerate}
\item
\begin{enumerate}
\item
Consider again the fingerprint $F_p(w) = w \bmod p$,
where we identify the integer
$w = 2^{n-1} w_{n-1} + \dots + 2w_1 + w_0 \in \N$
with the $n$-bit bitstring $w = \langle w_0,w_1,\dots,w_{n-1} \rangle$.
Fix $n,m \in \N$ with $n\quad\=If $X_{(i)}=Y$, return $i$.\\
3. \>Return ``No match.''
\end{tabbing}
Argue that this naive algorithm has a $O(mn)$ worst-case running time,
if we count each bit operation as one unit of time.
YOUR ANSWER GOES HERE.
\item Give a faster algorithm.
(Hint: make step \#2 more efficient.)
YOUR ANSWER GOES HERE.
\item
Suppose your algorithm is allowed to have a small chance (say, $< 1/m$)
of returning an erroneous answer.
Describe an algorithm with a $O(m \lg m)$ worst-case running time.
Your analysis of the running time can be somewhat informal, but
be sure to show all parameter choices.
(If you cannot find an algorithm with such a provable bound on the
running time, reduce the asymptotic running time as much as you are able.
Ignore constant factors.)
YOUR ANSWER GOES HERE.
\end{enumerate}
\end{enumerate}
\end{document}