1 files changed, 192 insertions, 0 deletions
diff --git a/howard/hw7.tex b/howard/hw7.tex
new file mode 100644
index 0000000..39d2f64
--- /dev/null
+++ b/howard/hw7.tex
@@ -0,0 +1,192 @@
+\newfam\bbold
+\def\bb#1{{\fam\bbold #1}}
+\font\bbten=msbm10
+\font\bbsev=msbm7
+\font\bbfiv=msbm5
+\textfont\bbold=\bbten
+\scriptfont\bbold=\bbsev
+\scriptscriptfont\bbold=\bbfiv
+
+\newcount\indentlevel
+\newcount\itno
+\def\reset{\itno=1}\reset
+\def\afterstartlist{\advance\leftskip by .5in\par\advance\leftskip by -.5in}
+\def\startlist{\par\advance\indentlevel by 1\advance\leftskip by .5in\reset
+\aftergroup\afterstartlist}
+\def\alph#1{\ifcase #1\or a\or b\or c\or d\or e\or f\or g\or h\or
+    i\or j\or k\or l\or m\or n\or o\or p\or q\or r\or
+    s\or t\or u\or v\or w\or x\or y\or z\fi}
+\def\li#1\par{\medskip\penalty-100\item{\ifcase\indentlevel \number\itno.\or
+                                  \alph\itno)\else
+                                  (\number\itno)\fi
+                           }%
+         #1\smallskip\advance\itno by 1\relax}
+\def\ul{\bgroup\def\li##1\par{\item{$\bullet$} ##1\par}}
+\let\endul\egroup
+\def\hline{\noalign{\hrule}}
+\let\impl\rightarrow
+\newskip\tableskip
+\tableskip=10pt plus 10pt
+\def\endproof{\leavevmode\quad\vrule height 6pt width 6pt
+depth 0pt\hskip\parfillskip\hbox{}{\parfillskip0pt\medskip}}
+\def\lcm{\mathop{\rm lcm}}
+
+\li Find the prime factorization of each of these integers.
+
+{\startlist
+
+\li 9072
+
+$9072 = 2^4\cdot 3^4\cdot 7.$
+
+\li 324
+
+$324 = 2^2\cdot 3^4.$
+
+\li 6!
+
+$6! = 2^4\cdot 3^2\cdot 5.$
+
+}
+
+\li Approximate the number of prime numbers not exceeding 50000. Show
+your work.
+
+The approximate number of primes less than $N$ is $N/\ln(N)$
+$${50000\over\ln(50000)} \approx {50000\over 10.82} \approx 4621.$$
+
+\li Determine whether the integers 2, 51, 101, and 119 are pairwise
+relatively prime. Show your work for full credit.
+
+These are the prime factorizations of the above numbers:
+
+$2 = 2.$
+
+$51 = 3\cdot 17.$
+
+$101 = 101.$
+
+$119 = 7\cdot 17.$
+
+$51$ and $119$ are not coprime because they share the factor 17.
+Every other pair is relatively prime.
+
+\li What is the greatest common divisors of these pairs of integers?
+
+{\startlist
+
+\li $2^4*3^3*5^6$ and $2^5*3^3*5^2*7^2.$
+
+$2^4*3^3*5^2.$
+
+\li 19 and $19^1 8.$
+
+19.
+}
+
+\li What is the least common multiple of these pairs of integers?
+
+{\startlist
+
+\li $2^4*3^3*5^6$ and $2^5*3^3*5^2*7^2.$
+
+$2^5*3^3*5^6*7^2.$
+
+\li $2^4*7$ and $5^5*13.$
+
+$2^4*5^5*7*13.$
+
+}
+
+\li Find the least integer with $n$ distinct positive factors where $n$
+is below. For example, if $n=4,$ then the solution is $6$ because
+$1,2,3,6$ are distinct positive factors of $6$ and there are $n=4$ of
+them.
+
+{\startlist
+
+\li 3
+
+$4$ has factors $1,2,4.$
+
+\li 5
+
+$16$ has factors $1,2,4,8,16.$
+
+\li 6
+
+$12$ has factors $1,2,3,4,6,12.$
+
+}
+
+\li Use the Euclidean algorithm to find the following values. You must
+clearly show all steps of your work using the Euclidean algorithm taught
+in class.
+
+{\startlist
+
+\li $\gcd(100,101)$
+
+$(100,101)\to (100, 1)\to (1, 0),$ giving $\gcd(100,101) = 1.$
+
+\li $\gcd(64, 12)$
+
+$(64, 12)\to (12, 4)\to (4, 0),$ giving $\gcd(64,12) = 4.$
+
+}
+
+\li Show your work by using the Chinese Remainder Theorem, find all
+values $x$ such that
+
+$x \equiv 1 \pmod{5}.$
+
+$x \equiv 2 \pmod{6}.$
+
+$x \equiv 3 \pmod{7}.$
+
+\smallskip
+5, 6, and 7 are pairwise coprime, so these congruences specify a unique
+integer $n$ such that $x\equiv n \pmod{210}.$
+
+$y_1 = 42,$ and $a_1 = 1,$ so $z_1 = 3.$
+
+$y_2 = 35,$ and $a_2 = 2,$ so $z_2 = 5.$
+
+$y_3 = 30,$ and $a_3 = 3,$ so $z_3 = 4.$
+
+$a_1y_1z_1 + a_2y_2z_2 + a_3y_3z_3 \equiv 206 \bmod{210}.$
+
+\li Decrypt the following ciphertext message: $HJUXDW,$ which was
+encrypted first using a shift cipher, then using a transposition cipher.
+The key of the shift cipher was $k=3,$ and the transposition cipher was
+based on the permutation $\sigma$ of the set 1, 2, 3 with $\sigma(1) =
+2$ and $\sigma(2) = 3$ and $\sigma(3) = 1.$
+
+We start by computing a transposition $\sigma^{-1}(3) = 2$ and
+$\sigma^{-1}(2) = 1$ and $\sigma^{-1}(1) = 3.$
+The ciphertext becomes $JUHDWX.$
+We then convert the ciphertext to numbers
+$(9, 20, 7, 3, 22, 23)$ and subtract three to get
+$(6, 17, 4, 0, 19, 20),$ and finally convert numbers to letters,
+obtaining $GREATU.$
+
+\li Suppose you intercept the message ``57 04 00 59 50 57 04 14 52 50 57
+42 00 54'' that has been encrypted using the RSA algorithm. You know
+that the public key used for encryption is $(65,7).$ Decrypt the message
+to determine what was said. Use the process shown in lecture to complete
+this problem. You must show all work. (If your calculator is unable to
+calculate $a^d\bmod{n}$ where a is one of the numbers in the message above and
+$d$ is the decryption key, then you can just show $a^d\bmod{n}$ for each value of
+a. Note that this is the final step in decryption so you won't show what
+the message actually was. You must still show the work for calculating
+the decryption key $d$).
+
+$n = 13\cdot 5 = p\cdot q.$
+$\lcm(p-1,q-1) = 12.$
+$7\cdot 7 \equiv 1 \pmod{12},$
+so $d = 7$ (the multiplicative inverse of 7 mod 12)
+
+We then compute $a^d\bmod{n}$ for each number in the message, obtaining
+$(8,4,0,19,15,8,4,14,13,15,8,3,0,24)$ or $IEATPIEONPIDAY.$
+
+\bye