<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass{article}[11 pts] 
\begin{document}

\centerline{\bf THEORY OF NUMBERS, Math 115 B}
\centerline{\bf Homework }
\vskip 5pt

\begin{enumerate}

\item Explain in your own words what is a public-key encryption
system.

\item What is the knapsack problem? 

\item (8.5.2) Show that if $a_1,a_2,\dots,a_n$ is a super-increasing
sequence, then $a_j \geq 2^{j-1}$ for $j=1,2,\dots,n$.

\item (8.5.6) Encrypt the message BUY NOW using the knapsack
cipher based on the sequence obtained from the super-increasing sequence
$(17,19,37,81,160)$ by performing modular multiplication with multiplier
$w=29$ and modulus $m=331$.

\item (9.1.4) Find a primitive root modulo each of the following integers:
4,5,10,13,14,18.

\item (9.1.5) Show that 20 has no primitive roots.

\item (9.1.16) Show that if r is a primitive root modulo the positive
integers $m$, then $r^{-1}$ is also a primitive root modulo $m$.

\item (9.2.1) Find the number of incongruent roots modulo 11 of each of the
following polynomials $x^2+10$ and $x^4+x^2+1$.

\item What is a discrete logarithm and why is it interesting for cryptographic
applications?

\end{enumerate}

\end{document}





</pre></body></html>