\documentclass[12pt]{amsart}

\input{../../TeX/macros}

\usepackage{fullpage}

\begin{document}

\title[Math 75 Homework \#7]{Math 75: Mathematical Cryptography \\ Homework \#7}
\date{Due Wednesday, 18 May 2016}

\maketitle

\section*{Problems}

\begin{problab}{1}
For the following integers either provide a witness for the compositeness of $n$ or conclude that $n$ is probably prime by providing $5$ numbers that are not witnesses.
\begin{enumalph}
\item $n=1009$.
\item $n=2009$.
\end{enumalph}
\end{problab}

\begin{problab}{2}
Using big-$O$ notation, estimate the number of bit operations required to perform the witness test on $n \in \Z_{>0}$ enough times so that, if $n$ passes all of the tests, it has less than a $10^{-m}$ chance of being composite. 
\end{problab}

\begin{problab}{3}
Factor $53477$ using the Pollard rho algorithm.
\end{problab}

\begin{problab}{4}\ 
Suppose that $n$ balls are randomly thrown into $m$ bins.
\begin{enumalph}
\item Approximately what is the probability that there is a bin with two balls in it, assuming $m$ is much larger than $n$?
\item What is the probability that there is a bin with no balls in it?  If $m$ is large, and $n$ is large in comparison to $m$, show that this probability is approximately $me^{-n/m}$.  \emph{[Hint: Use $\lim_{x \to \infty} (1+1/x)^x = e$.]}  

\item In terms of $m$, what is the smallest value of $n$ so that there is a $\geq 1/2$ chance that no bin is empty?  

\item Suppose you are asked to fill an auditorium with people so that every day is a birthday for some person in the auditorium.  What is the smallest number of people which gives you better than an even chance?
\end{enumalph}
\end{problab}

\begin{problab}{5}   
\begin{enumalph}
\item Find a nontrivial factorization of $n=999999999999999919$ by hand.
\item Let $n=2^{29}-1$.  Given that
\begin{align*} 
258883717^2 &\equiv -2\cdot 3 \cdot 5 \cdot 29^2 \\
301036180^2 &\equiv -3\cdot 5 \cdot 11 \cdot 79 \pmod{n} \\
126641959^2 &\equiv 2 \cdot 3^2 \cdot 11 \cdot 79
\end{align*}
discover a factor of $n$.
\end{enumalph}
\end{problab}



\end{document}