\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx, hyperref,varwidth}
\pagestyle{empty}
\newcommand{\st}{~\mid~}
\newcommand{\powerset}{\ensuremath{\mathcal{P}}}
\newcommand{\bAlg}[1]{\begin{center}\begin{varwidth}{\textwidth}
#1
\begin{enumerate}\setlength{\itemsep}{-3pt}}
\newcommand{\eAlg}{\end{enumerate}\end{varwidth}\end{center}}
%\name{}
\assignment{CSE 20 Homework 8}
\duedate{Due: Thursday, March 16 2017 at {\bf 11pm}}
\begin{document}
\begin{center}
\begin{minipage}[t]{6in}
\rule{\linewidth}{2pt}
{\sc Topics} Equivalence relations, congruence mod m, and applications.
\newline
{\sc Reading} Rosen Sections 9.1, 9.5, 4.1, 4.5, 4.6
\newline
{\sc Key Concepts} Binary relations, reflexivity, symmetry, transitivity, equivalence
relation, partition, equivalence class, congruence modulo m, modular arithmetic,
applying modular arithmetic to hash functions, applying modular arithmetic to ciphers.\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[1.] ({\bf 16 points})
\begin{itemize}
\item[(a)]
Compute the last digit of $(42)^{2017}$.
Justify your answer using modular arithmetic; do not simply plug in the numbers
into a calculator.
\item[(b)] Prove that for any prime number $p > 3$, either $p \equiv 1 \mod 6$ or $p \equiv 5 \mod 6$ .
\end{itemize}
\end{problem}
\begin{problem}[2.] ({\bf 10 points})
{\it Read the introduction to hashing functions on page 287 of the textbook.}
A commonly used {\bf hashing function} for assigning memory addresses to records
is $h: \{ possible input records \} \to \{0, \dots, m-1\}$ and
\[
h(k) = k \mod m
\]
where $m$ is the number of available memory locations.
This function is {\bf onto} the codomain of possible memory locations
$\{0, \ldots, m-1\}$ but may not be one-to-one. Two input values $a,b$ where
$a \neq b$ but $h(a) = h(b)$ result in a {\bf collision}.
\begin{itemize}
\item[(a)] Which memory locations are assigned by the hashing function
$h(k) = k \mod 101$ to the records given by Social Security numbers
\begin{itemize}
\item[(i)] 104578690
\item[(ii)] 372201919
\end{itemize}
\item[(b)] Find a Social Security number that would cause a collision
(under this same hashing function) with one of the numbers above. Use only
valid Social Security numbers, as described (by Wikipedia) as
\begin{quote}
Prior to June 25, 2011, a valid SSN could not have an area number between 734 and 749, or above 772, the highest area number the Social Security Administration has allocated. Effective June 25, 2011, the SSA assigns SSNs randomly and allows for the assignment of area numbers between 734 and 749 and above 772 through the 800s \ldots Some special numbers are never allocated:
\begin{itemize}
\item Numbers with all zeros in any digit group (000-\#\#-\#\#\#\#, \#\#\#-00-\#\#\#\#, \#\#\#-\#\#-0000).
\item Numbers with 666 or 900-999
\end{itemize}
\end{quote}
Justify your answer.
\end{itemize}
\end{problem}
\begin{problem}[3.] ({\bf 15 points})
{\it Read the introduction to cryptographic protocols on page 302 of the textbook.}
Cryptography is the process of hiding a message by encoding it in a
reverseable (decodable) way.
Many cryptographic schemes rely on modular arithmetic. Often, the two
parties who want to communicate in secret need to share a common piece
of information, called a key. Since messages are often encoded as numbers,
the key is typically an integer. The Diffie-Hellman algorithm lets Alice and Bob agree
on a shared secret number, without each one revealing their own secret to
the other. Here is the algorithm:
\begin{itemize}
\item Alice and Bob agree (in public) to
use a prime $p$ and an integer $a$ with $0 \leq a < p$.
{\it The numbers
$p$ and $a$ are not secret.}
\item Alice chooses a secret integer $k_1$ and sends $y_a = a^{k_1} \mod p$ to Bob.
\item Bob chooses a secret integer $k_2$ and sends $y_b = a^{k_2} \mod p$ to Alice.
\item Alice computes $(y_b)^{k_1} \mod p$.
\item Bob computes $(y_a)^{k_2} \mod p$.
\end{itemize}
{\it Note: in order for this to work properly, we need additional assumptions on $a$;
see textbook for details.}
\begin{itemize}
\item[(a)] Describe each steps (write out the results of all computations) that
Alice and Bob follow when they use the Diffie-Hellman key exchange protocol
to generate a shared key, using the prime $p=101$ and $a =2$. Assume
that Alice selects $k_1 = 7$ and Bob selects $k_2 = 9$. {\it You may use a calculator,
MATLAB, Wolfram Alpha, etc.\ so long as you include the results of intermediate
calculations.}
\item[(b)] What's Alice and Bob's shared secret number in this case? Explain why
they each got the same number.
\end{itemize}
\end{problem}
\vspace{10pt}
\noindent{\it Bonus - not for credit: read more about different cryptographic schemes in
Section 4.5 in the book.}
\begin{problem}[4.] ({\bf 9 points})
{\bf This question must be completed by each group member individually.}
Submit all responses together in a single image / PDF as usual.
\begin{itemize}
\item[(a)] Pick {\bf one} topic from CSE 20 that was challenging or particularly
interesting for you.
Describe the key idea or insight behind this concept. Your explanation should
sound as though you were
talking about this concept with a recruiter for a summer internship {\bf or} as
though your were tutoring this
class next quarter and motivating this concept to one of your students.Your
description should be roughly 200-400 words (one to two paragraphs) and
should include {\bf all} of the following elements.
\begin{description}
\item[Motivation] Why is this concept important or interesting?
\item[Definition] What are the key ideas in this concept?
\item[Strategy] What specifically did you do to understand this concept more deeply or
to overcome initial struggles with it? Give a specific example, analogy, or other technique
you used.
\end{description}
\item[(b)] Please complete the CAPE and TA evaluations. Once each group member
has done so (we're using the honor
system here), write out the statement ``We have all completed the end of quarter
evaluations" and you'll receive 3 points.
\end{itemize}
\end{problem}
\end{document}