\documentstyle[12pt,twoside,macpsfig,amssymb,amstex]{article}
\input{macros-course}
\parindent0pt
\parskip1.5ex

\begin{document}
\handout{notes4}{Notes 4}{September 21, 1995}

\setcounter{section}{6}

\renewcommand{\gcd}[2]{\mbox{GCD}(#1,#2)}

I blew some proofs last time!  No base case for Nim.

\section{Induction in Number Theory}

Number theory is about natural numbers: divisibility, primality,
fractions$\ldots$  

Number theory used to be for ``entertainment'' but has recently become
{\em very} important (more later).

\begin{defin}
$a$ {\em divides} $b$ (written $a \mid b$) when $(\exists c) b=ac$.  $b$ is
{\em divisible} by $a$.
\end{defin}

\begin{theorem}
\label{additive}
If $a \mid b$ and $a \mid c$, then $a \mid (b+c)$ and $a \mid (b-c)$.
\end{theorem}
\begin{proof}
By definition of divisibility, $(\exists t) b = at$ and $(\exists s) c
= as$.\\  Therefore, $b+c = at+as = a(t+s)$.\\  Therefore, by definition,
$a \mid b+c$.
\end{proof}

\begin{theorem}
\label{multiply}
If $a \mid b$ then $a \mid bc$ for any $c$.
\end{theorem}

\subsection{GCDs}

Remember die hard?  Why did $5$ and $3$ buckets work but $6$ and $3$
not?  What if buckets are $21$ and $133$, and goal is $13$ gallons?

\begin{defin}
The {\em greatest common divisor} of $x$ and $y$, written
$\gcd{x}{y}$, is the largest natural number $q$ such that $q\mid x$
and $q \mid y$.
\end{defin}

We can prove GCD is well defined.  A divisor always exists, and the
set of divisors is bounded above and this has a largest element (proof
by well ordering---any finite set has a largest element).  

GCD of $24$ and $36$? $21$ and $133$?

You will prove in homework: In die hard, buckets of size $x,y$ always
produced numbers divisible by GCD of $x$ and $y$.

\begin{theorem}
GCD of $x$ and $y$ has form $ax+by$ for some integers $a$ and $b$.
\end{theorem}
\begin{proof}
Let $S=\{l \mid l>0, l=ax+by, a,b \in \naturals\}$.  Let
$l=\min(S)=ax+by$ (exists since $S$ is nonempty---contains $x^2+y^2$).  Let 
$g=\gcd{x}{y}$.
\begin{itemize} 
\item $g \le l$.  Proof:  $g \mid x$ and $g \mid y$ means $g \mid ax+by=l$.
\item $g \ge l$.  It suffices to show $l$ is a common divisor, since
$g$ is greatest such.  Proof: First show $l \mid x$.  Write $x = ql+r$
by division algorithm.
\begin{eqnarray*}
r &= &x-ql\\
  &= &x - q(ax+by)\\
  &= &(1-qa)x + (-qb)y
\end{eqnarray*}
But, by division algorithm, $0 \le r < l$.  Thus $r \notin S$, so $r=0$.
Thus $l \mid x$.  Similarly, $l \mid y$.  Thus $l \mid ax+by$.
\end{itemize}
\end{proof}

\subsection{Euclid's Algorithm}

The above proof tells us gcd has a particular form, but it doesn't
tell us how to find it: it is a non-constructive existential proof (we
can't examine infinitely many $ax+by$).  An algorithm tells us how to
actually find the answer. Euclid's algorithm for GCD is one of the
first algorithms.

\newcommand{\Euclid}[2]{\mbox{Euclid}(#1,#2)}

\begin{defin}
$x \bmod y$ is the remainder on division of $x$ by $y$. 
\end{defin}
Note $x \bmod y$ is well defined by the division algorithm.  $x \bmod
y = x$, but for $y > 0$, we know that $0 \le x \bmod y < y$.

{\bf Procedure} $\Euclid{x}{y}$:
\begin{itemize}
\item if $y > x$, swap $x$ and $y$.
\item if $y=0$, then return $x$.
\item otherwise, return $\Euclid{x \bmod y}{y}$.
\end{itemize}

For any algorithm, there are two things to prove:
\begin{itemize}
\item it gives an answer (termination)
\item it gives the right answer (correctness)
\end{itemize}

\subsubsection{Termination}

\begin{theorem}
Euclid's algorithm terminates after at most $x+y$ steps.
\end{theorem}
\begin{proof}
  Strong Induction on $y$.  Let $P(y)$ be: $(\forall x) \Euclid{x}{y}$
  terminates in at most $y+1$ steps.  Base case: $y=0$.  We stop after
  1 step since we just return $x$.  Inductive step: Since $x \bmod y <
  y$, the value of the second argument to $\Euclid{y}{x\bmod y}$ is
  less than the value of the second argument to $\Euclid{x}{y}$.
  Therefore, the time taken for $\Euclid{x}{y}$ is one step to reduce
  to $\Euclid{y}{x \bmod y}$ plus (by strong induction) $x \bmod y +1
  \le y$ steps to solve the recursive subproblem.  Thus the total time
  is at most $y+1$, proving the induction step.
\end{proof}

Note that the above proof does induction one one variable while
holding the other variable fixed.  This is perfectly legitimate.  I
said ``by induction on $y$'' in the proof because there was potential
confusion regarding $x$. 

The proof relies on a reduction in the value of the second argument to
work.  We will use the same approach in the remaining theorems in this
section, but won't mention it again.

In class, I did a bad induction: I used a base case of $x=y=0$, which
was invalid because we never actually arrive at that case.  We stop as
soon as $y=0$, so I can't make an inductive step at that point.
Instead, I have to directly prove all possible base cases---that is,
any case where $y=0$ and $x$ has any value.

\subsubsection{Correctness}

How do we prove Euclid's algorithm works?  We show that it works ``at
each step.'' It follows by induction that it works all the way.

\begin{lemma}
$\gcd{x}{y}=\gcd{y,x\bmod y}$.
\end{lemma}
\begin{proof}
If $g \mid x$ and $g \mid y$, then $g \mid (x-qy)=r$ by
Theorem~\ref{additive}.  If $g \mid y$ and $g \mid r$, then $g \mid
(qy+r) = x$ by Theorem~\ref{additive}.  Therefore, $(x,y)$ and $(y,r)$
have same divisors; thus same GCD.
\end{proof}

\begin{theorem}
$\Euclid{x}{y} = \gcd{x}{y}$.
\end{theorem}
\begin{proof}
  By induction on $y$.  Inductive hypothesis: for all $x$,
  $\Euclid{x}{y} = \gcd{x}{y}$.  Base case: $y=0$ immediate from
  algorithm.  Inductive step: use previous lemma.
\end{proof}

\begin{example} We find $\gcd{949}{273}$.

\begin{verbatim}
     949  273  
3    273  130  
2    130   13  
10    13    0  
\end{verbatim}
\end{example}

\subsection{Finding GCD coefficients}

The previous algorithms finds the GCD.  It can be modified to give the
desired coefficients.

\newcommand{\Euclidb}[2]{\mbox{Euclid-Coefficients}(#1,#2)}
{\bf Procedure} $\Euclidb{x}{y}$ where $x\ge y$, $\gcd{x}{y} = g$.
\begin{itemize}
\item if $y=0$, return $(1,0)$.
\item Write $x = qy+r$
\item Use $\Euclidb{y}{r}$ to find $a,b$ such that $ay+br=g$.
\item Return $(b,a-qb)$ (claiming $bx+(a-qb)y =g$).
\end{itemize}

\begin{theorem}
$\Euclidb{x}{y}$ returns $a,b$ such that $ax+by = \gcd{x}{y}$.
\end{theorem}
\begin{proof}
Induction on $y$.  Say $\gcd{x}{y}=g$.  Base case $y=0$ trivial.
Otherwise, say $x=qy+r$.  By induction, recursive call returns $(a,b)$
with $ay+br=g$.  Then $g=ay+br = ay+b(x-qy) = bx+(a-bq)y$.
\end{proof}

\begin{example}
Table method for getting GCD and Coefficients: run Euclid's algorithm,
then fill in the coefficients from the bottom up.
\begin{verbatim}
     949  273    -2   7 
3    273  130     1  -2
2    130   13     0   1
10    13    0     1   0
\end{verbatim}
\end{example}

\subsection{RSA cryptosystem}

RSA is a {\em public key} cryptosystem: anyone can encrypt a message
to me, but no one can decrypt it:
\begin{itemize}
\item I find two large primes $p$ and $q$, set $n=pq$.

\item I find $e$,$d$ such that $ed \bmod (p-1)(q-1) = 1$

\item I publish $e,n$.

\item Given message $M$, coded message $C=M^e \bmod n$
can be computed by anyone, since $e,n$ are public. 

\item Given encoded message $C$, message $M=C^d \bmod n$.
\end{itemize}

The last step follows from the following theorem:
\begin{theorem}
$M^{ed} \bmod n = M$.
\end{theorem}
\begin{proof}
Textbook.
\end{proof}

No one knows how to ``break'' RSA:
\begin{itemize}
\item   No one knows how to compute $p,q$ efficiently from $n$.
\item   No one knows how to compute $d$ efficiently without $p,q$
(finding $d$ actually lets you find $p,q$).
\item   No one knows how to find $M$ efficiently without $d$ (ie,
solve $C=M^e$ for $M$). 
\end{itemize}

Where do we get $n$, $e$, and $d$?  There are fast algorithms for
generating large prime numbers $p$ and $q$, which of course gives
$n$.  But how do we find $e$ and $d$?  Recall our objective: if
$m=(p-1)(q-1)$, we want 
\[
de \bmod m = 1.
\]
In other words, $de=qm+1$.  Or, $de-qm = 1$.  From our discussion of
Euclid's algorithm, we see this equation has a solution (in
$\naturals$) if and only if $\gcd{e}{m} = 1$.  So we can pick any old
$e$, and so long as it is relatively prime to $m$ (which is almost
always the case) the above equation will have a solution that tells us
$d$.

Used by netscape.

\subsection{Fast Exponentiation}

In recitation, we will show how to compute the big exponentiations
needed to implement RSA quickly.  It relies on the fact that show
$x^{ab}\bmod n = (x^a \bmod n)^b \bmod n$.

\subsection{Factoring}

If we knew $p$ and $q$, it would be easy to find $d$ given $e$ and
break RSA.  So RSA relies on the ``hardness'' of factoring.  But maybe
we could find different primes $p'$, $q'$ such that $n=p'q'$?  If such
solution are common enough, then just trying lots of possibilities
might give us one.  Fortunately, the {\em Fundamental Theorem of
Arithmetic} shows that this isn't the case:

\begin{theorem}
Every number has a {\em unique} factorization into primes (except for
reordering the factors)
\end{theorem}

So the only way to factor $n$ is to find $p,q$.

\begin{lemma}
Let $p$ be a prime.  If $p \mid ab$, the $p \mid a$ or $p \mid b$.   
\end{lemma}
\begin{proof}
If $p \mid a$, we are done, so assume not.  It follows that
$\gcd{p}{a} = 1$ (since the only divisors of $p$ are $p$ and $1$, and
$p$ doesn't divide $a$).  It follows that there is an equation $sa+tp
= 1$.  It follows that $sab+tpb = b$.  But $p \mid sab$ (since $p\mid
ab$) and $p \mid tpb$, so $p \mid b$ (by Theorem~\ref{additive}).
\end{proof}

\begin{corollary}
Let $p$ be a prime.  If $p \mid a_ia_2\cdots a_k$, then $(\exists i)
p\mid a_i$.
\end{corollary}

\begin{proof} (of the fundamental theorem).
We proved last time that every number has a factorization.  We need to
show it is unique.  We argue by (strong) induction.  The base case
$n=1$ id trivial.  So suppose the claim true for all numbers less than
$n$.  Suppose one factorization is $n=p_1p_2\cdots p_k$,
with the $p_i$ written in nondecreasing order.  Suppose there is a
{\em different} factorization into primes $n=q_1q_2\cdots q_l$.  It
follows that $p_1 \mid q_1\cdots q_l$.  This, by the previous
corollary, $(\exists i) p_1 \mid q_i$.  But then $p_1 = q_i$, implying
two factorizations of $n/p_1$.  This contradicts our inductive
hypothesis, so the theorem if proved.
\end{proof}

Unique factorization gives another way to compute GCD: factor both
numbers, and multiply out all their common factors.  

\end{document}
