
\section{Induction and Recursive Algorithms}

We've spent a lot of time studying induction\.
This is because induction comes up all the time in analyzing
computation\.
Why?  Well, induction is a ``one step at a time'' proof method.
Computations also evolve ``one step at a time.''

In fact, many of our inductive proofs can be seen as \emph{algorithms}
for solving a problem\.  And many of our recursive definitions can be
seen as algorithms for computing a value.

We proved ``any $2^n$ by $2^n$ board can be tiled with Ls''\.  If you
look at the inductive proof, we actually gave a \emph{procedure} for
carrying out that tiling\.  We break the board in four, tile each
piece, and merge the tilings\.  What kind of algorithm is this? It's
\emph{recursive:} it calls itself on smaller subproblems.
Similarly the inductive proof for Nim gave a game-winning algorithm\.

The recursive definitions of the Fibonacci numbers is also expressing
a recursive algorithm for computing them\.  The same holds for the
factorial function, multiplication, etc.

Just about any inductive proof that a problem has a solution is in
fact providing a recursive algorithm for solving the problem\.

Similarly, when you have a recursive algorithm that you think solves
some problem, induction is the usual way to prove that it works.

\subsection{RSA}

RSA is at the core of many of the secure communication protocols we
use today (SSL, etc)\.  RSA works by treating any given message
(sequence of bits) as a big number $x$ and applying a mathematical
function that ``hides'' the number $x$ unless you know a secret key.

More precisely, it computes the remainder $r$ of $x^a$ on division by
$b$, where $a$ and $b$ are two specially constructed \emph{large}
numbers\.  It turns out that if someone is given $r$ and knows the
right secret about the origin of $a$ and $b$, they can ``invert'' the
exponentiation and get $x$\.  But if you don't have the secret, the
inversion seems to be very hard.

So, how can we compute the exponentiation?\\
The most obvious way is to work from the \emph{recursive definition}:
\begin{itemize}
\item $x^0=1$
\item $x^{n}=x\cdot x^{n-1}$
\end{itemize}
This is a definition of $x^n$, but also suggests a recursive algorithm
for computing it:
\begin{structproof}
  Procedure $\ms{Exp}(x,n)$\\
  \\
  {\bf if} $n=0$\\
  \> return 1\\
  {\bf else}\\
  \> return $x*\ms{Exp}(x,n-1)$
\end{structproof}
Now it's pretty ``obvious'', but how would you \emph{prove} that
algorithm $\ms{Exp}$ returns the right answer?\\
Well, it doesn't always: what happens if you call $\ms{Exp}(5,-2)$?
$\ms{Exp}(8,2.5)$?\\ 
(Trying to prove correctness can reveal implicit assumptions.  We
assume $n$ is a natural number).

\begin{theorem}
  For all $x,n \in \nats$, a call to $\ms{Exp}(x,n)$ returns $x^n$
\end{theorem}
Note: the procedure $\ms{Exp}$ above can be thought of as (i) a
computational process or (ii) a recursive function definition (defined
as the output of the computational process)\.  We need to prove that it
defines the \emph{same} function as $x^n$.

We are actually claiming two distinct things in the theorem:
\begin{description}
\item[Termination.] The algorithm returns something (i.e., doesn't run
  forever). 
\item[Correctness.] The algorithm returns the \emph{right} something.
\end{description}
\begin{proof}
  By induction on $n$\.  The base case, that $\ms{Exp}(x,0)$ returns
  $x^0=1$, follows by inspection: on that call, the ``if'' condition is
  satisfied, so we return 1\.  For the inductive step, assume
  $\ms{Exp}(x,n)$ returns $x^n$ and prove correctness for $n+1$\.
  Consider the call 
  to $\ms{Exp}(x,n+1)$\.  $n+1>0$, so the ``else'' clause is invoked\.  We
  call $\ms{Exp}(x,n)$ which, by assumption, returns $x^n$\.  We multiply
  that quantity by $x$, yielding $x^{n+1}$, and return it\.  This proves
  that $\ms{Exp}(x,n+1)$ terminates and returns the right value.
\end{proof}

OK, we've shown the procedure returns the right answer\.
Is it a good implementation?
How many multiplications are done to compute $x^n$?  By induction,
there are $n$ multiplications\.
Remember those ``128 bit keys'' we weren't allowed to export to
foreign countries?  That
means the number $n$ has about 128 bits\.
So we will be doing about $2^{128}$ multiplications\.
We'll still be working on it when 6.042 finishes...

\subsection{Fast Exponentiation}

Let's cut down on the number of multiplies\.  Suppose we want to
compute $x^a$ and $a$ is even, say $2c$\.  So we want to compute
$x^a=x^{2c}$\.  Is there any obvious way to beat $a$ multiplies?
Yes\. Note
$x^{2c}=(x^c)^2$\.  So let's compute $x^c$ ($c$ multiplies) and then
square it (1 multiply)\. This totals $c+1 =1+ a/2$ multiplies.

What if $a$ is odd? 

Let's generalize this idea to an algorithm:

\begin{proofoverhead}
  Procedure $\ms{FastExp}(x,n)$\\
  \\
  {\bf if} $n=0$\\
  \> return 1\\
  {\bf else}\\
  \> {\bf if} $n$ is even\\
  \> \> let $y=\ms{FastExp}(x,n/2)$\\
  \> \> return $y^2$\\
  \> {\bf else}\\
  \> \> let $y=\ms{FastExp}(x,(n-1)/2)$\\
  \> \> return $x*y^2$
\end{proofoverhead}

\begin{theorem}
  For all $x,n \in \nats$, a call to $\ms{FastExp}(x,n)$ returns $x^n$
\end{theorem}
\begin{proof}
  We'll use induction again.  The base case ($n=0$) follows by
  inspection as before\.  So let's prove the inductive step.

  What kinds of subproblems are we going to use to prove it works for
  $n$?  {\bf Not} just $n-1$, so let's use strong induction.

  Since it keeps the notation simpler, we will prove $P(n)$ from
  smaller cases instead of $P(n+1)$\.  Suppose the inductive
  hypothesis is true for every $k < n$, let's prove it for $n$\.
  Suppose we call $\ms{FastExp}(x,n)$\.  We can assume $n\ne 0$ (we
  already did a proof for 0) so the {\bf else} clause is selected in
  the algorithm\.  We consider two cases.

  If $n$ is even (say $n=2m$) then we  call
  $\ms{FastExp}(x,m)$\.   By strong induction this returns $x^m$, which
  we assign to $y$\.
  Then we return $y=(x^m)^2=x^{n}$ as required, so the proof works for
  this case.

  If $n$ is odd (say $n=2m+1$) then we call   $\ms{FastExp}(x,m)$ and
  set $y$ to the result\.  
  Then we return $x*y^2=x*(x^m)^2=x^{2m+1}=x^n$\.
  So the proof works in this case too\.
  These are all the cases.  QED.
\end{proof}

How many multiplications does {\bf this} algorithm do?

\begin{theorem}
  If $n$ has $b$ bits, then $\ms{FastExp}(x,n)$ performs at most $2b$
  multiplications.  
\end{theorem}
\begin{proof}
  Induction on $b$.\\
  Base case:  If $b=0$, then $n=0$ and we return without doing
  any multiplications.  So the base case is true.
  Inductive step: assuming it true for $b$ bits, consider a $b+1$-bit
  number $n$.\\
  We execute a recursive call to   $\ms{FastExp}$ on either $n/2$
  or $(n-1)/2$, depending whether $n$ is odd or even.\\
  Both of these numbers have at most $b$ bits.\\
  So by induction, the recursion does at most $2b$ multiplications.\\
  Then we do either one more (even case) or two more (odd case). So at
  most two more.\\
  Overall, at most $2b+2 = 2(b+1)$ multiplications.  QED.
\end{proof}

Using this algorithm, a 128-bit key means only 256 multiplications:
quite an improvement!


\subsection{Greatest Common Divisor}

\begin{definition}
Given 2 positive natural numbers, $a, b \in N^+$, their \emph{greatest
  common divisor (GCD)} is the largest number that divides both
without remainder.
\end{definition}

(Recall the notation: $a \mid b$ means $a$ divides $b$.)

Finding the  GCD is a problem that must be solved to generate the
``secret'' used to decrypt RSA messages.

One of the first recorded algorithms---Euclid's algorithm---finds
greatest common divisors\.  Here is a key lemma for ``simplifying''
the problem:

\begin{lemma}
  Given $x>y$, let $r=x-y$.  Then any common divisor of $x$ and $y$ is
  also a common divisor of $y$ and $r$, and vice versa.
\end{lemma}
\begin{corollary}
  GCD$(x,y)=$GCD$(y,r)$
\end{corollary}
\begin{proof} (of the corollary).  The pair s$(x,y)$ and $(y,r)$ have exactly
  the same set of divisors (by lemma).  Thus, the biggest number in
  each set, namely the greatest common divisor, is the same.
\end{proof}
\begin{proof} (of the lemma)\.  We prove one direction: that any
  divisor of $x$ and $y$ also divides $r$\.  Suppose $d \mid x$ and $d
  \mid y$\.  So $x=zd$ and $y=wd$\.  Thus $r=x-y=d(z-w)$ so $d \mid r$,
  meaning $d$ is a common divisor of $y$ (by assumption) and $r$ (by
  deduction)\.  The other direction of proof is similar.
\end{proof}

From this lemma we get Euclid's algorithm:
\begin{structproof}
  Procedure $\ms{Euclid}(x,y)$\\
  \\
  {\bf if} $x=0$ return $y$\\
  {\bf else if} $y=0$ return $x$\\
  {\bf else if} $x > y$ return $\ms{Euclid}(y,x-y)$\\
  {\bf else} return $\ms{Euclid}(x,y-x))$
\end{structproof}

Example: \\
Find $\ms{GCD}(112, 84)$ = ? \\
Step 1: $112 - 84 = 28$, reduce to $(28,84)$. \\
Step 2: $84 - 28 = 56$, reduce to $(28,56)$. \\
Step 3: $56 - 28 = 28$, reduce to $(28,28)$. \\
Step 4: $28 - 28 = 0$, reduce to $28,0$\\
Now done, answer is $28$. \\
\\

Let's prove this algorithm does the right thing\.
First faint worry: maybe we've got an infinite recursion?
The first thing to prove for any algorithm: it \emph{terminates}

\begin{lemma}
  For any natural number inputs $x$ and $y$, $\ms{Euclid}(x,y)$ returns
  a value.
\end{lemma}
Why do we think this is true intuitively?  Because the arguments
``shrink'' on each recursive call and eventually reach 0.  Induction
lets us formalize this.
\begin{proof}
  Induction on $x+y$\.  More formally, we prove by strong induction on
  $n$ that for all inputs $x$ and $y$ such that $x+y=n$, the algorithm
  terminates.

  Base case: if $x+y=0$, then $x$ is 0 so we return  immediately.

  Inductive step.  Assume the claim for $x+y<n$ and prove it for
  $x+y=n$\.
  Now consider two cases\.  Either $x \ge y$ or $y \ge x$.  

  Suppose first that $x \ge y$. So consider two subcases\.  If $y=0$,
  then we return immediately and the inductive step is proved\.  If $y
  > 0$, then we make a recursive call with arguments $y$ and $x-y <
  x-0 =x$\. So the sum of the two new arguments is less than
  $x+y=n$\. So the inductive hypothesis holds: the recursive call
  returns a value\. So our original call returns (the same) value.

  What about the second case ($y \ge x$)?  Well, I would have to write
  the same proof all over again, swapping $x$ and $y$ everywhere\.  To
  avoid such tedium, we say ``without loss of generality, assume $x
  \ge y$\.  This is code for ``the other case works exactly the same
  way'' and completes the proof.
\end{proof}

\begin{lemma}
  For any natural number inputs $x$ and $y$, $\ms{Euclid}(x,y)$
  returns GCD$(x,y)$.
\end{lemma}
\begin{proof}
  We'll use induction on $x+y$ as before.  The base case of $x+y=0$ is
  trivial (assuming we define GCD$(0,0)$ to be 0, which seems fair).

  For the inductive step where $x+y= n > 0$, assume without loss of
  generality that $x \ge y$\.  If $y=0$, we return $x$, which is the
  correct answer\.  If $y>0$, then we return the result of a recursive
  call on $\ms{Euclid}(y,x-y)$\.  This means (by strong induction) that
  we return GCD$(y,x-y)$\.  But we proved in a lemma above that
  GCD$(x,y)=$GCD$(y,x-y)$\. So we are returning the right value, namely
  GCD$(x,y)$.
\end{proof}

One might be concerned about the GCD$(0,0)$ definition\.  Technically
every number is a common divisor of 0 and 0, so it should be infinite?

But this turns out not to matter\.  We never actually make a recursive
call to $(0,0)$---as soon as one argument is 0, we terminate.  

So even though we still need a base case for the induction pattern, we
never actually apply that base case\.  Instead our real base case is
implicit in the ``subcase'' of the inductive step where one argument
is 0.

This is an example of a hack to the definition or algorithm that makes
the proof cleaner\.  If we wanted to avoid considering GCD$(0,0)$, we
could prove by induction that any call to $\ms{Euclid}(x,y)$ that
\emph{does not have both arguments equal to 0} returns the correct
value\.  However, we would then have to waste time on our induction
step checking that this extra condition was still satisfied in the
recursion\.  By making an arbitrary, unimportant definition of
GCD$(0,0)$, we save ourselves some work.

As described, Euclid's algorithm may perform as many as $x$
substractions (when $y=1$)\.  A small variation on our
algorithm---using remainder on division by $y$ instead of subtracting
$y$---can dramatically speed up the algorithm\.  It turns out that
with this change, only $2\log x$ divisions are needed to solve the
problem.
