Marisol Ontiveros edited untitled.tex  about 10 years ago

Commit id: 439fc83957841cd2bd974d3ef829fe46ac849082

deletions | additions      

       

\textit{Oh, an empty article!}   You can \input{macros.tex}  \begin{document}  \centerline{\large \bf CS/MATH111 ASSIGNMENT 2}  \centerline{due Tuesday, April~29 (8AM)}  \vskip 0.1in  \noindent{\bf Individual assignment:} Problems 1 and 2.  \noindent{\bf Group assignment:} Problems 1,2 and 3.  \vskip 0.1in  %%%%%%%%%%%%%%%%%%%%%%%%%%%%  \begin{problem}  Let $x$ be a positive integer and $y = x^2+2$. Can $x$ and $y$ be both prime? The answer is yes,  since for $x=3$ we  get started by \textbf{double clicking} this text block and begin editing. You can also click the \textbf{Insert} button below to add new block elements. Or you can \textbf{drag and drop an image} right onto $y=11$, and both numbers are prime. Prove that  this text. Happy writing! is the only value of  $x$ for which both $x$ and $y$ are prime.  \smallskip  \noindent\emph{Hint:} Consider cases, depending on the remainder of $x$ modulo $3$.  \end{problem}  %%%%%%%%%%%%%%%%%%%%%%%%%%%%  \begin{problem}  Alice's RSA public key is $P = (e,n) = (13,77)$.  Bob sends Alice the message by encoding it as follows.  First he assigns numbers to characters:  blank is 2, comma is 3, period is 4, then  A is 5, B is 6, ..., Y is 29, and Z is 30. Then he  uses RSA to encode each number separately.   \smallskip  Bob's encoded message is:  \begin{verbatim}  11 58 52 30 57 61   60 22 30 10 26 35   52 23 30 10 41 22   23 52 38 30 52 12   58 46 30 57 61 60   30 35 26 46 30 50   41 23 52 61 22 52   30 52 12 58 73 30   26 23 30 57 61 60   30 69 37 58 26 23   58 53  \end{verbatim}  Decode Bob's message. Notice that you don't have Bob's secret key, so you  need to ``break" RSA to decrypt his message.  \smallskip  For the solution, you need to provide the following:  %  \begin{itemize}  %  \item Describe step by step how you arrived at the solution:  \begin{itemize}  \item Show how you determined $p$, $q$, $\phi(n)$, and $d$;  \item Show the computation for the first number in the message.  \end{itemize}  %  \item Give Bob's message in plaintext. (The message is a quote. Who said it?)  %  \item If you wrote a program, attach your code to the hard copy.  If you solved it by hand, attach your scratch paper with calculations.  %  \end{itemize}  \end{problem}  %%%%%%%%%%%%%%%%%%%%%%%%%%%%  \begin{problem}  (a) Compute $14^{-1}\pmod{19}$ by enumerating multiples of the number and the modulus.  Show your work.  \smallskip\noindent  (b) Compute $14^{-1}\pmod{19}$ using Fermat's theorem. Show your work.  \smallskip\noindent  (c) Find a number $x\in\braced{1,2,...,40}$  such that $7x \equiv 11 \pmod{41}$. Show your work.  (You need to follow the method covered in class; brute-force checking  all values of $x$ will not be accepted.)  \end{problem}  %%%%%%%%%%%%%%%%%%%%%%%%%%%%  \vskip 0.1in  \paragraph{Submission.}  To submit the homework, you need to upload the pdf file into ilearn by 8AM on Tuesday,  April~29, and turn-in a paper copy in class.  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  \end{document}