\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{listings}
\usepackage{xcolor}

\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}
 
\lstdefinestyle{mystyle}{
    backgroundcolor=\color{backcolour},   
    commentstyle=\color{codegreen},
    keywordstyle=\color{magenta},
    numberstyle=\tiny\color{codegray},
    stringstyle=\color{codepurple},
    basicstyle=\footnotesize,
    breakatwhitespace=false,         
    breaklines=true,                 
    captionpos=b,                    
    keepspaces=true,                 
    numbers=left,                    
    numbersep=5pt,                  
    showspaces=false,                
    showstringspaces=false,
    showtabs=false,                  
    tabsize=2
}
 
\lstset{style=mystyle}
\lstset{language=Python}

\newcommand{\kgmcomment}[1]{}
\renewcommand{\gcd}{\mathrm{gcd}}


\begin{document}
\headers{Math373}{Homework 8}{Due Wed, Mar. 22, 2023}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\makeatletter
\def\@oddfoot{}
\makeatother

\newcommand{\K}{\mathcal{K}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\C}{\mathcal{C}}


\newcommand{\ord}{\mathrm{ord}}
\newcommand{\F}{\mathbb{F}}

\noindent
\textbf{Directions:} Solve the following problems.  All written work must be your own.  See the course syllabus for detailed rules.

\begin{enumerate}

\item {} [JJJ 2.8] Alice and Bob agree to use the prime $p=1373$ and the base $g=2$ for communications using the ElGamal public key cryptosystem.
\begin{enumerate}
	\item Alice chooses $a=947$ as her private key.  What is the value of her public key?
	\item Bob chooses $b=716$ as his private key, so his public key is $B = 2^{716} = 469$.  Alice encrypts the message $m=583$ using the random element $t=887$.  What is the ciphertext $(c_1, c_2)$ that Alice sends to Bob?
	\item Alice decides to choose a new private key $a=299$ with associated public key $A=2^{299} = 34$.  Bob encrypts a message using Alice's public key and sends her the ciphertext $(661, 1325)$.  Decrypt the message.
	\item Now Bob chooses a new private key and publishes the associated public key $B = 893$.  Alice encrypts a message using this public key and sends the ciphertext $(693, 793)$ to Bob.  Eve intercepts the transmission.  Help Eve by solving the discrete logarithm problem $2^b \equiv 893 \pmod{1373}$ and use the value of $b$ to decrypt the message.
\end{enumerate}

\item {} Let $m$ be a positive integer and let $g\in \Z_m^*$.
\begin{enumerate}
	\item Let $h$ be the order of $g$ in $\Z_m^*$.  Prove that if $g^n \equiv 1\pmod{m}$, then $h\mid n$. 
	\item Let $n$ be a positive integer.  Prove that the order of $g$ in $\Z_m^*$ equals $n$ if and only if $g^n \equiv 1\pmod{m}$ and $g^{n/q} \not\equiv 1\pmod{m}$ for each prime $q$ that divides $n$.
\end{enumerate} 

\item Alice and Bob wish to use the ElGamal cryptosystem to communicate, and they are having difficulty deciding on a prime/base pair $(p,g)$.  The pairs that they are considering are $(345601, 71482)$ (option A), $(516163, 482305)$ (option B), and $(177007, 145014)$ (option C).  Which option do you recommend for Alice and Bob, and why?

\item {} Shanks's Algorithm By Hand.  Let $p=211$ and let $g=8$.
\begin{enumerate}
	\item Find the order $N$ of $g$ in $\F_p$.
	\item Compute List 1 in Shanks's Algorithm for computing $\log_g(h)$.
	\item Use Shanks's Algorithm to find each of the following discrete logarithms.  In each case, explicitly give List 2.
	\begin{multicols}{3}
	\begin{enumerate}
		\item $\log_g(122)$
		\item $\log_g(150)$
		\item $\log_g(200)$
	\end{enumerate}
	\end{multicols}
\end{enumerate}

\item {} Shanks's Algorithm By Computer.
\begin{enumerate}
	\item Implement Shanks's Baby-step/Giant-step algorithm $\texttt{shanks\_discrete\_log(g,h,m)}$ that returns $x$ such that $g^x \equiv h \pmod{m}$ when such an $x$ exists.  Submit your code.  
	
	Hint: if implementing the algorithm in python, then you may find the built-in dictionary class useful.  See \texttt{shanks.py} for code that makes a dictionary storing the first few powers of a base $g$ and a naive, brute-force implementation $\texttt{naive\_discrete\_log(g,h,m)}$.
	\item Let $p = 84298814015219$.  Use your code to compute $\log_2(3)$ in $\F_p$.  With a good implementation, it should take no more than about a minute on modern hardware.  (My laptop from about 2016 takes 6 or 7 seconds.)
\end{enumerate}

\item Solve the following systems of congruences.
\begin{enumerate}
	\item \begin{align*}
		x &\equiv 18 \pmod{25}\\
		x &\equiv 7 \pmod{11}\\
		x &\equiv 16 \pmod{32}
	\end{align*}
	
	\item \begin{align*}
		17x &\equiv 8 \pmod{43}\\
		6x &\equiv  41 \pmod{55}\\
		5x &\equiv 4 \pmod{9}
	\end{align*}

	\item \begin{align*}
		7x &\equiv 33 \pmod{145}\\
		11x &\equiv 44 \pmod{45}\\
		17x &\equiv 38 \pmod{75}
	\end{align*}
	Caution: The given moduli are not pairwise relatively prime (for example, $3\mid 45$ and $3 \mid 75$), so CRT does not apply directly.
\end{enumerate}


\end{enumerate}
\end{document}
