\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\newif\ifanswer
\answertrue
\head{CS5800}{Algorithms}{Spring 2011}{26 January 2011}{2}

\begin{center}
\Large{\bf Quiz 1}
\end{center}

{\bf Problem 1. (7 points) Modular Double Exponentiation}

In class and text, we have seen algorithms for several arithmetic
operations -- addition, multiplication, division, exponentiation,
modular arithmetic.  The following table lists the running times you
may assume for all the operations listed over any three $n$-bit
numbers $a$, $b$, and $c$.
\begin{center}
\begin{tabular}{||l|c||}
\hline
Operation & Running time\\
\hline
{\sc Add}$(a,b,c)$: $a + b \bmod c$ & $O(n^2)$ \\
{\sc Multiply}$(a,b,c)$: $a \cdot b \bmod c$ & $O(n^2)$ \\
{\sc Power}$(a,b,c)$: $a^b \bmod c$ & $O(n^3)$\\
\hline
\end{tabular}
\end{center}

In this exercise, we study the double exponentiation procedure in
modular arithmetic.  Give an algorithm {\sc Double-Exponent} that
takes as input four $n$-bit positive integers $x$, $y$, $z$, and $p$,
where $p$ is {\em known to be prime}, and returns $x^{y^z} \bmod p$.
State its running time, in terms of $n$, using the big-Oh notation.

\begin{itemize}
\item Give your algorithm in pseudo-code.  You may use any of the
  operations listed in the table above in your algorithm.  You may
  also use any other operation or material we have covered in class.
\item Make the running time of your algorithm as small as possible.
  Most important, however, is to give a correct procedure and state
  the correct running time for your procedure, even if it may not be
  the optimal achievable.

\item You {\em do not need}\/ to prove the correctness of your
  algorithm or formally establish its running time.
\end{itemize} 

\ifanswer
{\bf Answer:} Here are two solutions for {\sc Double-Exponent}(x,y,z,p)
\begin{enumerate}
\item
{\sc Power}$(x,\mbox{{\sc Simple-Power}}(y, z), p)$.

\item
{\sc Power}$(x,\mbox{{\sc Power}}(y, z, p-1), p)$.
\end{enumerate}

Let us consider Solution 1.  In the above, {\sc Simple-Power}$(a,b)$
simply computes $a^b$ without taking the modulus with respect to any
number.  As shown in text, exponentiation $y^z$ can be done with
$O(\log z) = O(n)$ multiplications.  These multiplications, however,
are of large numbers: if $y$ and $z$ both have $n$ bits, then $y^z$
can be as large as $(2^n)^{2^n}$, which can have as many as $n2^n$
bits; so the cost of some of the multiplications could be as high as
$O((n2^n)^2) = O(n^2 2^{2n})$.  Therefore, the time taken by {\sc
  Simple-Power} can be bounded by $O(n^3 2^{2n})$.  And the time taken
by {\sc Power} is $O(n^3 2^{3n})$ since the exponent could have as
many as $n2^n$ bits.  So the total time is $O(n^3 2^{3n})$.  This is a
correct solution, but too inefficient.

Solution 2 is much more efficient and makes use of the fact that $p$
is prime.  By Fermat's Little Theorem $x^{p-1} \bmod p = 1$ for $1 \le
x < p$.  So we only need to compute the power $y^z$ modulo $(p-1)$.
This ensures that all calculations use numbers at most $n$ bits.  The
running time of Solution 2 is $O(n^3) + O(n^3) = O(n^3)$.

\fi

{\bf Problem 2. (3 points)} Prove or disprove: For any positive
integers $a$ and $b$ with $a \ge b$,

\[
\gcd(a+b,a-b) \ge \gcd(a,b).
\]

(If you are proving the statement, a 2-3 sentence proof in English
should suffice.  If you are disproving the statement, you need to give
values for $a$ and $b$ for which the above claim is not true.)

\ifanswer 
{\bf Answer:} 
The claim is true.  If ${a=b}$, the claim holds since
$\gcd(a+b,a-b) = \gcd(2a,0) = 2a > \gcd(a,a)$.

If ${a>b}$, suppose we denote $\gcd(a,b)$ by $t$. So we have
\begin{eqnarray*}
{a = x \cdot t, \;\; b = y \cdot t}
\end{eqnarray*}
in which x and y are all integers. Then we have
\begin{eqnarray*}
{a+b = (x+y)t, \;\; a-b = (x-y)t}
\end{eqnarray*}

So $t$ is a common divisor of $(a+b)$ and $(a-b)$, which implies
\begin{eqnarray*}
{\gcd(a+b,a-b) \ge t = \gcd(a,b)}.
\end{eqnarray*}

\fi
\end{document}