\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 13}{Due Wed, Apr 27, 2022}

%\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{\ZZ}{\mathbb{Z}}
\renewcommand{\O}{\mathcal{O}}

\newcommand{\ord}{\mathrm{ord}}
\newcommand{\F}{\mathbb{F}}
\renewcommand{\poly}[1]{\mathbf{#1}}

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

\begin{enumerate}

\item Let $p=281$.  Given the following polynomials $\poly{a}$ and $\poly{b}$ in $\F_p[x]$, use a computer program to compute polynomials $\poly{d}$, $\poly{u}$, $\poly{v}$ in $\F_p$ such that $\gcd(\poly{a},\poly{b}) = \poly{d} = \poly{u}\poly{a} + \poly{v}\poly{b}$.  Python classes for working with polynomial rings are given in the supplementary file \texttt{polynom.py}.
\begin{enumerate}
	\item $\poly{a} = x^5 - x^2 + 6x -14$\\
	$\poly{b} = x^3 + 9x^2 + x - 1$
	
	\item $\poly{a} = x^6 + x^5 - x^4 + 6x^3 + 2x^2 - 5x + 10$\\
	$\poly{b} = x^7 + 2x^5 + 2x^4 - 2x^3 + 6x^2 - x + 2$
\end{enumerate}

\item Let $p=53$.  For the following triples $(\poly{a},\poly{b},\poly{f})$, compute $\poly{a}\poly{b}$ in the quotient ring $\F_p[x] / \poly{f}$.  You may check your work with a computer, but these computations should be done \textbf{by hand}.
\begin{enumerate}
	\item $\poly{a} = 4x^5 - x^4 + 25x^3 + 18x^2 + 45x + 10$, $\poly{b} = 1$, $\poly{f} = x^3$
	\item $\poly{a} = 4x^5 - x^4 + 25x^3 + 18x^2 + 45x + 10$, $\poly{b} = 1$, $\poly{f} = x^3 - 1$
	\item $\poly{a} = 3x+2$, $\poly{b} = x + 22$, $\poly{f} = x^2 + x + 1$
\end{enumerate}

\item Let $p=37$, and let $\poly{f} = x^{7} - 1$.  For each $\poly{a}$ in $\F_p[x] / \poly{f}$, either find the inverse $\poly{a}^{-1}$ or explain why the inverse does not exist.  A computer program is needed for some (but not all) of these.
\begin{multicols}{4}
\begin{enumerate}
	\item $\poly{a} = 8$
	\item $\poly{a} = 0$
	\item $\poly{a} = x$
	\item $\poly{a} = x + 1$
	\item $\poly{a} = x + 2$
	\item $\poly{a} = x^2 - 1$
	\item $\poly{a} = x^2 + 1$
	\item $\poly{a} = x^3 + x^2 + 1$
\end{enumerate}
\end{multicols}


\item Alice and Bob agree to use the NTRU cryptosystem with public parameters $(N,p,q,d) = (7,37,479,2)$.  Use a computer program to solve the following problems.  
\begin{enumerate}
	\item Alice chooses $\poly{f} = x^5 - x^4 + x^2 - x + 1$ and $\poly{g} = x^6 + x^4 - x^2 - x$ as her private key.  What is her public key $\poly{h}$?
	\item Bob wants to send the message $\poly{m} = 4x^6 - 18x^5 + 7x^2 + x + 1$ to Alice and selects $\poly{r} = x^6 + x^3 - x - 1$ as his random element.  What is the corresponding ciphertext $\poly{c}$? 
	\item The next day, Alice receives the ciphertext $\poly{c} = 350x^6 + 4x^5 + 415x^4 + 221x^3 + 276x^2 + 464x + 197$ from Bob.  What message did Bob send?
\end{enumerate} 

\end{enumerate}
\end{document}
