\documentclass{article}
\usepackage{amsmath}                            % want AMS fonts
\usepackage{amssymb}                            % use AMS symbols
\usepackage[ruled]{algorithm2e}
\usepackage{url}
\input{p}

%=================================================================
% My macros
%=================================================================
\newcommand{\Zstar}[1]{\ensuremath{\mathbb{Z}_{#1}^*}}


\begin{document}
\homework{4}{February 14, 2007}{February 21, 2007}{Anna Lysyanskaya}
For a more in-depth treatment of this material, see Victor Shoup's
book {\underline{A Computational}\\
{\underline{Introduction to Number Theory and
Algebra}}, freely available for downloading at
\url{http://shoup.net/ntb/}.

The following notation is useful for this homework:

\begin{definition}
Let $n$ be an integer.  $\Zns$ denotes the set of integers such that
$x \in \Zns$ iff $1 \leq x \leq n$ and $\gcd(x,n)=1$.
\end{definition}




\problem{Extended Euclidean GCD Algorithm}

On input integers $x$ and $y$,
the extended Euclidean GCD algorithm finds integers $a$ and $b$
such that $ax+by = \gcd(x,y)$.  This is done by careful bookkeeping
throughout the execution of the Euclidean GCD algorithm, and is
described in more detail in Shoup, Chapter 4.

\begin{alphabetize}
\item Use Euclid's algorithm to compute $\gcd(254, 366)$ 
\item Use extended Euclidean Algorithm to find $L, K$ such that $16L + 35K=1$.
\item Find $16^{-1} \mod 35$.
\item Find $84^{-1} \mod 143$.  
\end{alphabetize}


\problem{Practice with Chinese Remainder Theorem}
In class we saw a simplified version of the Chinese Remainder Theorem,
where $n$ was the product of 2 primes.  But this can be extended to
allow $n = \prod_{i=1}^k n_i$ (as long as the $n_i$ are relatively
prime).  For a review of the Chinese Remainder Theorem, see Section
2.2 in Shoup.

Let $n = 11 *13 *16$.
Suppose that we know that :
$$x \equiv 8 \mod 11$$
$$x \equiv 2 \mod 13$$
$$x \equiv 7 \mod 16$$

Let's use the Chinese remainder theorem to find $x \mod n$.
\begin{alphabetize}
\item Use extended Euclid's algorithm to find $a,b$ such that $1 = a*11 + b*13*16$.  
\item Use extended Euclid's algorithm to find $a,b$ such that $1 = a*13 + b*11*16$.  
\item Use extended Euclid's algorithm to find $a,b$ such that $1 = a*16 + b*11*13$.

\item Use CRT to find $x \mod 11*13*16$.  
\end{alphabetize}


\problem{Micali's Primality Test}
\begin{lemma}
Let $n=pq$ be an RSA modulus.  Every square $a^2 \in \Zstar{n}$
has exactly four square roots:
$(a \bmod{p}, a \bmod{q})$,
$(a \bmod{p}, -a \bmod{q})$,
$(-a \bmod{p}, a \bmod{q})$, and
$(-a \bmod{p}, -a \bmod{q})$.
\end{lemma}

\begin{lemma}[Fermat's Little Theorem]
Let $p$ be a prime, and $a\in \Zstar{p}$.  Then $a^{p-1}\equiv 1 \mod p$.
\end{lemma}

In this problem, we will look at Micali's primality test.
Suppose $SQRT(a,p)$ is a polynomial-time algorithm that, if
$p$ is prime and $a \in \Zstar{p}$ is a quadratic residue,
outputs some square root of $a \bmod{p}$.
\begin{alphabetize}
\item Prove that the following algorithm is a primality test:
on prime input it outputs PRIME with high probability
and on composite input it outputs COMPOSITE with probability
at least $1/2$.

Algorithm:

Input: $n$ an integer
\begin{itemize}
\item If $n = 2$, output PRIME;
\item If $n$ is even, output COMPOSITE;
\item If $n$ is of the form $n=p^b$ for some $p,b>1$, output COMPOSITE;
\item Choose a random $r \in \{ 1, \ldots, n-1 \}$,
      If $gcd(r,n)>1$, output COMPOSITE;
\item $x \leftarrow SQRT(r^2 \bmod{n}, n)$;
If $x = \pm r \bmod{n}$, output PRIME; Else output COMPOSITE;
\end{itemize}

\item Suppose $p=4m+3$ is a prime and that $a$ is a quadratic
residue modulo $p$.  Prove that $a^{m+1}$ is a square root of
$a$ modulo $p$.
\item Use (a) and (b) to devise a primality testing algorithm
for integers equal to 3 modulo 4.
\end{alphabetize}




\end{document}