\documentclass[12pt]{article}

\usepackage{hyperref}

\usepackage{amssymb, amsmath, lineno, amsthm, pdfsync, bbm, graphicx}
\usepackage{MnSymbol,wasysym}


\tolerance=2000
\textwidth 6.55in
\textheight 9.0in
\oddsidemargin 0.001in
\evensidemargin 0.001in
\topmargin -0.4in

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{theoremnonum}{Theorem} 
\newtheorem{definition}{Definition}[section] 
\newtheorem{lemma}[theorem]{Lemma} 
\newtheorem{corollary}[theorem]{Corollary} 
\newtheorem{claimnonum}{Claim} 
\newtheorem{mycomment}{comment}[section] 
\newtheorem{conjecture}[theorem]{Conjecture} 
\newtheorem{problem}{Problem} 
\newcommand{\finishproof}{~$\Box$}
\newtheorem{remark}{Remark} 


\newcommand{\AND}{\; \wedge \;}

\newcommand{\SAT}{{\sf SAT}}
\newcommand{\DTIME}{{\sf DTIME}}
\newcommand{\NTIME}{{\sf NTIME}}
\newcommand{\DSPACE}{{\sf DSPACE}}
\newcommand{\NSPACE}{{\sf NSPACE}}
\newcommand{\EE}{{\sf E}}
\newcommand{\EXP}{{\sf EXP}}
\newcommand{\NEXP}{{\sf NEXP}}
\newcommand{\PSPACE}{{\sf PSPACE}}
\newcommand{\eL}{{\sf L}}
\newcommand{\NL}{{\sf NL}}
\newcommand{\LOGSPACE}{{\sf LOGSPACE}}
\newcommand{\Pe}{{\sf P}}
\newcommand{\NP}{{\sf NP}}
\newcommand{\coNP}{{\sf coNP}}
\newcommand{\FP}{{\sf FP}}
\newcommand{\PH}{{\sf PH}}
\newcommand{\CH}{{\sf CH}}
\newcommand{\PP}{{\sf PP}}
\newcommand{\num}{{\sf\#}}
\newcommand{\numP}{{\sf\#\Pe}}
\newcommand{\ParP}{{\mbox{$\oplus$\Pe}}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}} 
\newcommand{\C}{\mathbb{C}}
\newcommand{\R}{\mathbb{R}} 
\newcommand{\ket}[1]{{|{#1} \rangle}} 
\newcommand{\bra}[1]{{\langle {#1}|}}
\newcommand{\bracket}[2]{{\langle {#1} | {#2} \rangle}}
\newcommand{\nb}{{\bf {\sf n}}} 
\newcommand{\Xb}{{\bf {\sf X}}}
\newcommand{\Xbi}{{\Xb}_i}
\newcommand{\Xbj}{{\Xb}_j}
\newcommand{\nbt}{{\tilde{\nb}}}
\newcommand{\nbi}{{\nb_i}}
\newcommand{\nbj}{{\nb_j}}
\newcommand{\nbti}{{\tilde{\nb}_i}}
\newcommand{\nbtj}{{\tilde{\nb}_j}}
\newcommand{\Sb}{{{\bf{\sf S}}}}
\newcommand{\Cb}{{\bf {\sf C}}}
\newcommand{\Zb}{{\bf {\sf Z}}}
\newcommand{\Yb}{{\bf {\sf Y}}}
\newcommand{\Hb}{{\bf {\sf H}}}
\newcommand{\Ub}{{\bf {\sf U}}}
\newcommand{\Ufb}{{\bf {\sf U}}_f}
%\newcommand{\gcd}{{\mbox{\rm gcd}}}

\sloppy
 
\begin{document}
\thispagestyle{empty}
% The paper really starts here.

\noindent {\bf Assignment 4}\\
\noindent DUE: Thursday, 4/6/2023, work in pairs.\\[-0.2in]

\begin{enumerate}
\item Consider the group $G_{11}$, which (since 11 is prime) is the same as $\Z^*_{11} = \{1,2,3,4,5,6,7,8,9,10\}$ with multiplication mod 11.
\begin{enumerate}
\item Write down the multiplication table of $G_{11}$. 
\item List at least two elements that generate the entire group.
\item  List at least two elements that generate a proper subgroup of $G_{11}$, and verify that their order divides the order of the full group.
\end{enumerate}
\item Write down the group multiplication table for $G_{24}$. What are the inverses of each element?
\item\label{item:euclid} The Euclidean Algorithm amounts to the simple relation
$\gcd(a,b) = \gcd(b, a \bmod{b})$. By iterating this, the second argument decreases until one reaches 0, in which case the first argument is the $\gcd$. Algorithmically,\\[-0.5in]
{\tt
\begin{tabbing}
\=~~\=~~\=~~\=~~\=~~\=~~\=~~\=~~\=~~\=~~\=~~\=~~\=~~\\
\>\>gcd (a, b)\\
\>\>\{\\[-0.06in]
\>\>\>if b == 0 then\\
\>\>\>\>\{\\[-0.06in]
\>\>\>\>\>return a;\\[-0.06in]
\>\>\>\>\}\\
\>\>\>else\\
\>\>\>\>\{\\[-0.06in]
\>\>\>\>\>d = gcd(b, a mod b);\\[-0.03in]
\>\>\>\>\>return d;\\[-0.06in]
\>\>\>\>\}\\[-0.06in]
\>\>\}\\[-0.3in]
\end{tabbing}
}

B{\'e}zout's Lemma, which is proved, for example, in the document 
\url{https://mathcs.clarku.edu/~fgreen/courses/cs201/latexDemo.pdf},
says that for $a, b \in \Z$, there exist $x, y \in \Z$ such that
$\gcd(a,b) = ax + by$. 
\begin{enumerate}
\item Show that the Euclidean Algorithm can be extended, given $a$ and $b$,
to determine $x$ and $y$. Mermin describes this in a very sketchy way in Appendix J (Section J.2). Formalize the algorithm more 
precisely, either via pseudocode (which can be done by ``dressing up" the algorithm given above), or a careful description of the process.
\item An immediate consequence of the Extended Euclidean Algorithm is that
if $\gcd(a, b) = 1$, we can find $x, y \in \Z$ such that $ax + by = 1$.
Show how this leads to an algorithm for determining the inverse of $a$
mod $b$ (or the inverse of $b$ mod $a$). 
\end{enumerate}

\item
Let's play RSA! Suppose Bob randomly selects  primes $p = 59,$ $q = 101,$ 
and coding key $c = 41$. Using $c$, Alice sends him the encoded message $b = 250$. We, as Bob,
want to decode it. You may use a calculator for this problem, for multiplication and modular arithmetic, but 
try to do as much of it as possible by hand. In particular, trace through
the Euclidean Algorithm and its extension, and see how repeated squaring works
for powering mod $N$.
\begin{enumerate}
\item Compute $N = pq$ and\footnote{The notation $\phi$ is not arbitrary, since it is used for the ``Euler totient function," usually denoted $\phi$, such
that $\phi(n) = $ the number of natural numbers $< n$ that are relatively prime to $n$.} $\phi = (p-1)(q-1)$.
\item Using the Euclidean Algorithm, verify that $c \in G_\phi$, i.e.,
that $\gcd(c, \phi) = 1$.
\item Using the extension of the Euclidean Algorithm worked out in Problem~\ref{item:euclid}, compute the inverse of $c$ mod $\phi$, i.e., find $d$
such that $cd \equiv 1\pmod{\phi}$. 
\item Alice sends Bob the message $b = 250$. Decrypt it to determine
Alice's original uncoded message $a$. I.e.,
via repeated squaring, compute 
$a = b^d \pmod{N}$.
\end{enumerate} 

\item Prove that the Quantum Fourier Transform $\Ub_{\mbox{\rm\tiny FT}}$ is unitary.
Recall that,
\begin{eqnarray*}
  \Ub_{\mbox{\rm\tiny FT}}\ket{x}_n = \frac{1}{2^{n/2}}
             \sum\limits_{y=0}^{2^n-1} e^{\frac{2\pi i xy}{2^n}}\ket{y}_n.
\end{eqnarray*}
So your task reduces to proving that
\begin{eqnarray*}
  \Ub_{\mbox{\rm\tiny FT}}^{\dagger}\Ub_{\mbox{\rm\tiny FT}}\ket{x}_n = \ket{x}_n
  ~~~~\mbox{\rm~~~or~~~}~~~~  \Ub_{\mbox{\rm\tiny FT}}^{\dagger}\Ub_{\mbox{\rm\tiny FT}} = 1,
\end{eqnarray*}
for any $0 \le x \le 2^n - 1$. 

\end{enumerate}

\end{document}
