\bigskip
\textit{\textbf{Note:} This homework consists of two parts. The first part (questions 1-6) will be graded and will determine your score for this homework. The second part (questions 7-8) will be graded if you submit them, but will not affect your homework score in any way. You are strongly advised to attempt all the questions in the first part. You should attempt the problems in the second part only if you are interested and have time to spare.}
\rule{6in}{2px}
\begin{center}
For each problem, justify all your answers unless otherwise specified.
\end{center}
\section*{Part 1: Required Problems}
\bigskip
\Question {The Last Digit}
In each case show your work and justify your answers.
\begin{Parts}
\Part If $9k+5$ and $2k+1$ have the same last digit for some natural number $k$, find the last digit of $k$.
\Part If $S = \sum_{i=1}^{19}i!$, then find the last digit of $S^2$.
\Part Denote the last digit of a natural number $a$ by $b$. Show that the last digit of $a^n$ is the same as the last digit of $b^n$ where is $n\ge1$ is a natural number.
\Part Inspired by part (c), show that the last digit of $a^{4k+1}$ for all natural numbers $k$ is the same as the last digit of $a$. [Euler's Theorem is not allowed.]
\end{Parts}
\Question {Modular Arithmetic Problems}
In each case show your work and justify your answers.
\begin{Parts}
\Part For natural numbers $a$, show that $7a+3$ and $5a+2$ are coprime.
\Part What is $3^{48} \pmod{11}$?
\Part Solve $x^2+x\equiv2 \pmod{4}$.
\Part If $17x^{12}+5x^7-14x^{40}\equiv6 \pmod 7$, find $x$.
\Part If $a+4c\equiv 2b \pmod{21}$, simplify $100a+10b+c \pmod{21}$.
\end{Parts}
In parts (c), (d), and (e) give your solutions as integers mod m.
\Question{Check Digits: ISBN} In this problem, we'll look at a real-world applications of check-digits.
International Standard Book Numbers (ISBNs) are 10-digit codes ($d_1d_2\ldots d_{10}$) which are assigned by the publisher.
These 10 digits contain information about the language, the publisher, and the number assigned to the book by the publisher.
Additionally, the last digit $d_{10}$ is a "check digit" selected so that $\sum_{i=1}^{10} i \cdot d_i \equiv 0 \pmod{11}$.
(\textit{Note that the letter X is used to represent the number 10 in the check digit.})
\begin{Parts}
\Part Suppose you have a very worn copy of the (recommended) textbook for this class. You want to list it for sale online but you can only read the first nine digits: 0-07-288008-? (the dashes are only there for readability). What is the last digit? Show your work.
\nosolspace{1cm}
\Part Wikipedia says that you can determine the check digit by computing $\sum_{i=1}^9 i\cdot d_i \pmod{11}$. Show that Wikipedia's description is equivalent to the above description.
\nosolspace{1cm}
\Part Prove that changing any single digit of the ISBN will render the ISBN invalid. That is, the check digit allows you to \textit{detect} a single-digit substitution error.
\nosolspace{1cm}
\Part Can you \textit{switch} any two digits in an ISBN and still have it be a valid ISBN? For example, could 01\underline{2}34\underline{5}678X and 01\underline{5}34\underline{2}678X both be valid ISBNs? Explain.
\nosolspace{1cm}
\end{Parts}
\Question{Product of Two}
Suppose that $p>2$ is a prime number and $S$ is a set of numbers between $1$ and $p-1$ such that $|S|>p/2$, i.e. $(\forall x\in S) (1\le x\le p-1)$.
Prove that any number $1\leq x\leq p-1$ can be written as the product of two (not necessarily distinct) numbers in $S$, mod $p$.
\Question{RSA with Just One Prime}%
Given the message $x \in \{0, 1, \ldots, N-1\}$ and $N = pq$, where $p$ and $q$ are prime numbers, conventional RSA encrypts $x$ with $y = E(x) \equiv x^e$ (mod $N$). The decryption is done by $D(y) \equiv y^d$ (mod $N$), where $d$ is the inverse of $e$ (mod $(p-1)(q-1)$). \\
% Consider again the cast from Note 6.
% The cast from Note 6 is back!
Alice is trying to send a message to Bob, and as usual, Eve is trying to decipher what the message is.
One day, Bob gets lazy and tells Alice that he will now use $N = p$, where $p$ is a 1024-bit prime number, as part of his public key.
He tells Alice that it's okay, since Eve will have to try out $2^{1024}$ combinations to guess $x$.
It is very likely that Eve will not find out the secret message in a reasonable amount of time!
In this problem, we will see whether Bob is right or wrong.
Assume that Eve has found out about this new setup and that she knows the public key.
Similar to the original method, for any message $x \in \{0,1, \ldots, N-1\}$, $E(x) \equiv x^e$ (mod $p$), and $D(y) \equiv y^d$ (mod $p$). Choose $e$ such that it is coprime with $p-1$, and choose $d \equiv e^{-1}$ (mod $p-1$). \\
\begin{Parts}
% In this new setting, write out the modified encryption and decryption equations in terms of the message $x$, the encrypted message $y$, and the 1024-bit prime $N$. Show how you choose $e$ and $d$ in the encryption and decryption function, respectively.
\Part Prove that the message $x$ is recovered after it goes through your new encryption and decryption functions, $E(x)$ and $D(y)$.
\Part
Can Eve compute $d$ in the decryption function? If so, by what algorithm and approximately how many iterations does it take for it to terminate?
\Part
Given part (b), how would Eve recover $x$ and what algorithm would she use? Approximately how many iterations does it take to terminate?
\Part
Based on the previous parts, can Eve recover the original message in a reasonable amount of time? Explain.
\end{Parts}
% From Spring 2014 HW6
\Question{RSA for Midterm Scores}
Alice wants to tell Bob her midterm score, $m$, which is an integer between $0$ and $100$ inclusive. She wants to tell Bob over
an insecure channel that Eve can listen in on, but Alice does
not want Eve to know her midterm score.
\begin{Parts}
\Part Bob announces his public key $(N = pq, e)$, where $N$
is large (512 bits). Alice encrypts her message using RSA.
Eve sees the encrypted message, and figures out what Alice's
midterm score is. How did she do it?
\Part Alice decides to be a bit more elaborate. She picks a
random number $r$ that is $256$ bits long, so that it is
too hard to guess. She encrypts that and sends it to Bob,
and also computes $rm$, encrypts that, and sends it to Bob.
Eve is aware of what Alice did, but does not know the value
of $r$. How can she figure out $m$?
\end{Parts}
\bigskip
\textit{\textbf{Note:} This concludes the first part of the homework. The problems below are optional, will not affect your score, and should be attempted only if you have time to spare.}
\rule{6in}{2px}
\bigskip
\section*{Part 2: Optional Problems}
\bigskip
\Question{Just Can't Wait}
Joel lives in Berkeley. He mainly commutes by public transport, i.e., bus and BART.
He hates waiting while transferring, and he usually plans his trip so that he can get on his next
vehicle immediately after he gets off the previous one (zero transfer time, i.e. if he gets off his previous vehicle at 7:00am he gets on his next vehicle at 7:00am).
Tomorrow, Joel needs to take an AC Transit bus from his home stop
to the Downtown Berkeley BART station, then take BART into San Francisco.
\begin{Parts}
\Part \label{q:a}
%Suppose a bus arrives at Joel's home stop every 22 minutes from 6:05am onwards,
%it takes 10 minutes on the bus to get to the Downtown Berkeley BART station,
%and that a train arrives the station every 8 minutes from 4:25am onwards.
The bus arrives at Joel's home stop every 22 minutes from 6:05am onwards,
and it takes 10 minutes to get to the Downtown Berkeley BART station.
The train arrives at the station every 8 minutes from 4:25am onwards.
What time is the earliest bus he can take to be able to transfer to the train immediately?
Show your work. (Find the answer without listing all the schedules.)
%\qitem Suppose that the Bay Area became really crowded and both AC Transit and BART changed their schedules.
%The start time for both the Joel's bus and BART would remain the same,
%but the bus would run every 11 minutes and BART every 7 minutes instead.
%What would be the earliest bus that allows Joel zero transfer time?
\Part
%Suppose Joel actually has to take a Muni bus after he gets off the BART station in San Francisco,
%the commute time on BART is 33 minutes,
%and the Muni bus arrives that BART station every 17 minutes from 7:12am onwards.
Joel has to take a Muni bus after he gets off the train in San Francisco. The commute time on BART is 33 minutes, and the Muni bus arrives at the San Francisco BART station every 17 minutes from 7:12am onwards.
What time is the earliest bus he could take from Berkeley to ensure zero transfer time for both transfers?
If all bus/BART services stop just before midnight, is it the only bus he can take that day? Show your work.
\end{Parts}
\Question{Quantum Factoring}
We're pretty sure that classical computers can't break RSA (because it is hard to factor large numbers on them), but we know that quantum computers theoretically could. In this question, we will prove a fact that is a key part of Shor's Algorithm, a quantum algorithm for factoring large numbers quickly\footnote{Read more at \url{https://en.wikipedia.org/wiki/Shors_algorithm}.}.
Let $N = pq$ where $p,q$ are primes throughout this question.
\begin{Parts}
\Part
Prove that, for all $a \in \mathbb{N}$, there are only four possible values for $gcd(a, N)$.
\Part
Using part (a), prove that, if $r^2 \equiv 1 \mod N$ and $r \not \equiv \pm 1 \pmod N$ (i.e. $r$ is a "nontrivial square root of 1" mod $N$), then $gcd(r-1, N)$ is one of the prime factors of $N$.\\
\textit{Hint: $r^2 = 1 \mod N$ can be rewritten as $r^2 - 1 = 0 \mod N$ or $(r+1)(r-1) = 0 \mod N$.}
\end{Parts}