\documentstyle[10pt]{article}

\textwidth=6in
\oddsidemargin=0.25in
\evensidemargin=0.25in
\topmargin=-0.1in
\footskip=0.8in
\parindent=0.0cm
\parskip=0.3cm
\textheight=8.00in
\setcounter{tocdepth} {3}
\setcounter{secnumdepth} {2}
\newtheorem{theorem}{Teorema}
\newtheorem{exercise}{Ejercicio}
\newtheorem{corollary}{Corolario}
\newtheorem{lemma}{Lema}
\newtheorem{observation}{Observaci\'on}
\newtheorem{comentary}{Comentario}
\newtheorem{proposition}{Proposici\'on}
\newtheorem{definition}{Definici\'on}
\def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}}
\newcommand{\qedbox}{\vbox{\hrule\hbox{\vrule\squarebox{.667em}\vrule}\hrule}}
\newcommand{\qed}{\nopagebreak\mbox{}\hfill\qedbox\smallskip}
\newcommand{\startproof}{\noindent{\em Dem:}\hspace{1em}}
\newenvironment{dem}{\startproof}{\qed}
\newenvironment{proof}{{\bf Dem:}\hspace{1em}}{\qed}

\newcommand{\catedra}[4]{
   \pagestyle{headings}
   \thispagestyle{plain}
   \newpage
   \noindent
   \begin{center}
   \makebox[0in]{\framebox{
      \vbox{
    \hbox to 6in { {\bf MA-53G Intr. a la Criptograf\'{\i}a
			\hfill Semestre Oto\~no, 1998}  }
       \vspace{4mm}
       \hbox to 6in { {\Large \hfill C\'atedra No. #1 : #2 \hfill} }
       \vspace{2mm}
       \hbox to 6in { {\it Transcriptor: #3 \hfill} }
      }
   }}
   \end{center}
   \markboth{C\'atedra No. #1 : #2}{C\'atedra No. #1 : #2}
   \vspace*{4mm}
}

% LISTA DE MACROS PERSONALES COMIENZA AQUI

\renewcommand{\emph}[1]{{\em #1}}
\newcommand{\plain}{{\cal P}}
\newcommand{\cipher}{{\cal C}}
\newcommand{\key}{{\cal K}}
\newcommand{\encrip}{{\cal E}}
\newcommand{\decrip}{{\cal D}}
\newcommand{\nodiv}{\!\!\not|}

\newcommand{\modulo}{{\cal Z}}
\newcommand{\kernel}{\mbox{\rm Ker}}
\newcommand{\determ}[1]{\mbox{\rm det}(#1)}
\newcommand{\mcd}[2]{\mbox{\rm mcd}(#1,#2)}
\newcommand{\mcm}[2]{\mbox{\rm mcm}(#1,#2)}
\newcommand{\set}[2]{\{#1\,|\,#2\}}
\newcommand{\smidge}{{\kern .05em}}     
\newcommand{\Colon}{{\smidge\colon\;\:}}
\newcommand{\eqdef}{\stackrel{\rm def}{=}}
\newcommand{\mypmod}[1]{\,(\mbox{\rm mod}\,#1)}

\newcommand{\chapref}[1]{\mbox{Cap\'{\i}tulo~\ref{#1}}}
\newcommand{\secref}[1]{\mbox{Secci\'on~\ref{#1}}}
\newcommand{\ssecref}[1]{\mbox{Secci\'on~\ref{#1}}}
\newcommand{\apref}[1]{\mbox{Ap\'endice~\ref{#1}}}
\newcommand{\thref}[1]{\mbox{Teorema~\ref{#1}}}
\newcommand{\defref}[1]{\mbox{Definici\'on~\ref{#1}}}
\newcommand{\corref}[1]{\mbox{Corolario~\ref{#1}}}
\newcommand{\lemref}[1]{\mbox{Lema~\ref{#1}}}
\newcommand{\propref}[1]{\mbox{Proposici\'on~\ref{#1}}}
\newcommand{\figref}[1]{\mbox{Figura~\ref{#1}}}
\newcommand{\tablref}[1]{\mbox{Tabla~\ref{#1}}}
\newcommand{\eqref}[1]{\mbox{(\ref{#1})}}
\newcommand{\ineqref}[1]{\mbox{(\ref{#1})}}
\newcommand{\comref}[1]{\mbox{Comentario~\ref{#1}}}

% FIN LISTA DE MACROS PERSONALES

\begin{document}

% LOS DATOS IDENTIFICATORIOS DE LA CATEDRA TRANSCRITA VAN AQUI
\catedra{3}{23 de Marzo}{Felipe Saint-jean\footnotemark}

\footnotetext{Estoso apuntes est\'an basados en la transcripci\'on de
Marcos Kiwi (7/8/96} 
% TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI

\section{Divisibilidad y el Algoritmo de Euclides}
%
En esta secci\'on recordaremos algunas definiciones y repasaremos
  algunos resultados que conciernen a los n\'umeros enteros.

Dados dos enteros $a$ y $b$ decimos que $a$ \emph{divide a} $b$, o $b$
  \emph{es divisible por} $a$, y escribimos $a|b$ si existe un entero
  $k$ tal que $b=ak$. 
En este caso decimos que $a$ es un divisor de $b$.
Si $a$ no es un divisor de $b$ escribimos $a\nodiv b$.

Se tienen las siguientes propiedades:
\begin{itemize}
\item Si $a|b$ y $c$ es un entero, entonces $a|b\,c$.
\item Si $a|b$ y $b|c$, entonces $a|c$.
\item Si $a|b$ y $a|c$, entonces $a|(b \pm c)$.
\end{itemize}
Notemos que esta relaci\'on as\'{\i} definida, no es relaci\'on de orden,
pero de esta manera es valida para cualquier %A%,%B% y %C% enteros..
Cada entero $b$ mayor que $1$ tiene al menos dos divisores: $1$ y $b$.
Un divisor no trivial de $b$ es un divisor de $b$ distinto de $1$ y de $b$.
Un n\'umero \emph{primo} es, por definici\'on, un n\'umero mayor que $1$
  que no tiene divisores no triviales.
Un n\'umero es \emph{compuesto} si es mayor que $1$ y 
  tiene al menos un divisor no trivial.
\begin{theorem}
El Teorema Fundamental de la Aritm\'etica nos dice que cualquier n\'umero
  entero positivo se puede expresar de manera \'unica (salvo el orden 
  de los factores) como un producto de primos. Sea m entero:
% \begin{displaymath}
     \[m=\prod_{i=1}^{n}p_{i}^{e_{i}} \]
% \end{displaymath}
 donde $p_{i}$ son los factores primos, y $e_{i}$ son las veces que
 se repite el  $i$-\'esimo factor.
\end{theorem}

Dos consecuencias de este importante teorema son:
\begin{itemize}
\item Si $p$ es primo y $p|(ab)$, entonces $p|a$ o $p|b$.
\item Si $m|a$ y $n|a$, y $m$ y  $n$ 
  no tienen divisores comunes mayores que $1$,
  entonces $(mn)|a$.
\end{itemize}

El \emph{maximo com\'un divisor} de dos enteros $a$ y $b$ no ambos
  nulos, denotado por $\mcd{a}{b}$, es el mayor entero $d$ tal que
  $d|a$ y $d|b$. Equivalentemente, $d=\mcd{a}{b}$ si cualquiera sea el
  entero positivo $c$ tal que $c|a$ y $c|b$ se tiene que $c|d$.
 Es facil ver que el m\'aximo com\'un divisor es \'unico, ya que
 de haber dos, uno ser\'a mayor que el otro. Tambi\'en notemos que
 $\mcd{a}{b}$=$\mcd{b}{a}$.


El \emph{minimo com\'un multiplo} de dos enteros no nulos $a$ y $b$,
  denotado $\mcm{a}{b}$, es el menor entero positivo divisible por $a$ y $b$.
No es dificil probar que $\mcm{a}{b} = |a\,b|/\mcd{a}{b}$. 

Dados dos enteros $a$ y $b$, si conocemos los factores primos de ambos,
podemos calcular el \emph{maximo com\'un divisor} entre ambos n\'umeros
de la siguiente forma.  Si \[ a = \prod_{p\epsilon B} p^{\alpha _{p}}, b
= \prod_{q\epsilon A} q^{\alpha _{q}} \]     
  entonces 
 \[ \mcd{a}{b} = \prod_{p\epsilon A\cap B}^{} p_{i}^{min(\alpha _{p},\beta_{p})} \]

Donde $A$ es el conjunto de factores de $a$, $B$ es el conjunto de factres
de $b$ , $\alpha _{p}$ el n\'umero de veces que se repite el factor $p$ en la
factorizaci\'on de $a$, y $\beta _{p}$ el n\'umero de veces que $p$ esta
en
la
factorizaci\'on de $b$.
El problema de este m\'etodo es que no se sabe c\'omo obtener los factores
primos de un n\'umero de manera eficientemente. Es decir el mejor
algoritmo conocido toma un tiempo exponencial, que en 
general, no nos sirve. Este inconveniente da origen alsiguiente
algoritmo.

\subsection{Algoritmo de Euclides}
%
Sean $u$ y $v$ dos enteros no ambos nulos, definimos la funci\'on
recursiva

\begin{tabbing}
lllllllllllllllllllllll\=llll\=llll\=                \kill
                \>     Euclid(u,v)                      \\
                \> \>        if ($v=0$) then                \\
                \> \> \>           return ($|u|$)                  \\
                \> \>          else return (Euclid(b,u mod b))\\
                \>     end:
\end{tabbing} 

El algoritmo Euclid retorna el $\mcd{u}{v}$, y para eso se basa en dos
hechos fundamentales:
\begin{itemize}
\item $d|u$ y $d|v$ si y s\'olo si  $d|v$ y $d|$($u$ mod $v$), que es
lo
que se conoce como el invariante de la iteraci\'on.
\item $\mcd{a}{0}=a$, que es la condici\'on de salida de la iteraci\'on.
\end{itemize}

Es claro que este algoritmo termina, ya que $(a$ mod $b)<b$, es decir en
cada iteraci\'on el argumento de la funci\'on $Euclid$ disminuye. Si
suponemos $b>a$ (sin perder generalidad, ya que siempre podemos suponer
que un n\'umero es mayor que el otro y al mayor lo llamamos b) el
algoritmo termina en $O(b)$ iteraciones. Como entragamos al algoritmo la
representacion binaria de $a$ y $b$, el tama\~no de la entrada es
$O(log(b))$,  entonces el tiempo que demora el algoritmo ,que es $O(b)$, 
es exponencial en el tama\~no de la entrada. Queda claro que esta primera
aproximaci\'on no nos sirve y nesesitamos algo mejor. Veamos una cota mas
fina para el algoritmo.

\section{An\'alisis del peor caso para el algoritmo de Euclides}
\begin{proposition}
Sean $u$,$v$ con $u > v>0$ tal que Euclid(u,v) termina en $n$ iteraciones,
se tiene que
$u\geq F_{n+2}$, $v\geq F_{n+1}$. Donde $F_{n}$ es la suceci\'on de
Fibonacci con $F_{0}=0$ y $F_{1}=1$.

\end{proposition}
\begin{proof}
Lo demostraremos por inducci\'on sobre n:\\
Caso base, n=1.\\ El algoritmo itera solo una vez, es decir $u=kv$ con k
entero.
Como el algoritmo iter\'o una vez (es decir no sali\'o en la
primera condici\'on $v=0$) se tiene que $v \geq 1$,
entonces, como $u>v$, se tiene$u\geq 2$.
Como $F_{2}=1$ y $F_{3}=2$, tenemos lo que buscabamos.\\
Paso inductivo:\\
Lo que haremos es suponer que se comple de la segunda iteraci\'on hasta la 
\'n$-esima$ y concluiremos que se cumple en la primera tambi\'en. 
Suponemos cierto para $n-1$, entonces sabemos que $v>F_{n+1}$ y $(u$ mod
$v)$  $> F_{n}$,
 como $u = \lfloor \frac{u}{v} \rfloor v+(u$ mod $v) \geq v+(u$ mod $v)$, 
desigualdad que se comple ya que  $u>v$ lo que implica $\frac{u}{v}>1$. 
Podemos ver que $u>F_{n+1}+F_{n}=F_{n+2}$, compliendose lo que buscabamos. 
\end{proof}

\begin{exercise}

 Pruebe que
\begin{eqnarray*}
F_{n} & = & \frac{1}{\sqrt{5}}\,(\phi^{n}-\varphi^{n})\,,
\qquad \mbox{ donde } \phi = \frac{1}{\sqrt{2}}\,(1+\sqrt{5})\,,
\ \ \varphi = \frac{1}{\sqrt{2}}\,(1-\sqrt{5})\,.
\end{eqnarray*}
Luego, para $n$ suficientemente grande $F_{n}$ es el entero m\'as cercano
  a $\phi^{n}/\sqrt{5}$. \newline
\end{exercise}

\begin{lemma}
Sean $u$, $v$ con $u>v>0$, y sea $E(u,v)$ el n\'umero de iteraciones que
toma $Euclid(u,v)$ entonces $E(u,v)<c_{1}\log{u}+c_{2}+c_{3}u^{-1}-2$
,
donde $c_{1}=1/\phi$ $\approx 2.08$, $c_{2}=\log{\sqrt{5}}/\log{\phi
}\approx 1.67$, y
$c_{3}=(1/\sqrt{5})\log{\phi} \approx 0.93$.
Tambi\'en $E(u,v)<c_{1}\log{v}+c_{2}-2+c_{3}v^{-1}$.
\end{lemma}
\begin{proof}
 Sea $u \geq F_{n+2}$, entonces

\[
u \geq \frac{\phi ^{n+2}-\varphi ^{n+2}}{\sqrt{5}}
 \geq 
\frac{\phi ^{n+2}-1}{\sqrt{5} } 
\]
 
entonces, usando que $\log{x+1}=\log{x}+\log{(1+1/x)} \geq \log{x}+1/x$
tenemos que

\[ \log{\sqrt{5} u + \frac{1}{\sqrt{5} u}} \geq \log{\sqrt{5}u+1} \]

obteniendo

\[ \log{\sqrt{5}u + \frac{1}{\sqrt{5}u}} \geq (n+2)\log{\phi } \]

despejando $n$ obtenemos que 

\[ n\geq \frac{\log{( \sqrt{5}u)}}{\log{(\phi  )}}+\frac{1}{\sqrt{5}\log{(\phi ) }u}-2
\]

concluyendo, luego de agrupar las constanes, que $n\geq
c_{1}\log{u}+c_{2}-2+c_{3}u^{-1}$\\
la otra desigualdad se demuestra de manera similar.

\end{proof}

Para ver la eficiencia podemos, como primera aproximaci\'on, contar el n\'umero de 
multiplicaciones, pero eso no nos sirve, ya que la eficiencia de la multiplicaci\'on
depende del tama\~no de los multiplicandos, entonces, si los n\'umeros
van creciendo, las multiplicaciones del final ser\'an mucho mas costosas que
las primeras. Es decir el costo de multiplicar no es constante. Para
evitar
ese inconveniente, contaremos las operaciones binarias
del algoritmo, que si son a tiempo constante.
Ya que operaremos con n\'umeros muy grandes, queremos multiplicar eficientemente.
Veremos (en la catedra 4) que calcular $uv$ requiere $O(\log{u}\log{v})$ 
operaciones binarias.

\begin{proposition}
El algoritmo de Euclides, en la entrada $(u,v)$, requiere
$O(\log{u}log{v})$  
operaciones binarias.
\end{proposition}
\begin{proof}
Primero definamos una funci\'on que mide el largo de un numero o el 
n\'umero de bits que requiere representarlo (sin incluir el bit del
signo):\\

\[ tam(n)= \left\{ \begin{array}{ll}
		   1   & \mbox{si $n=0$} \\
		   (\lfloor log_{2} \left| n \right| \rfloor )+1  &
\mbox{si $n>0$}
		   \end{array}
	   \right. \]


Veamos que podemos reescribir el algoritmo de euclides de la siguiente
manera:
$u_{0}=u$, $u_{1}=v$
\begin{tabbing}

llllllllllllllllllllllllll
\=llllllllllllllllllllllllllllllllllllllllllllll \=
\kill
\> $u_{0} =a_{0} u_{1} + u_{2}$   \>  $a_{0} = \lfloor u_{0}/u_{1}
\rfloor$  
\\
\>$u_{1}=a_{1}u_{2}+u_{3}$  \>  $a_{1}=\lfloor u_{1}/u_{2} \rfloor$ 
\\
\>...\\
\>$u_{i-2}=a_{i-2}u_{i-1}+u_{i}$ \> $a_{i-2}= \lfloor
u_{i-2}/u_{i-1}\rfloor$
\\
\>...\\
\\
\>$u_{n-1}=a_{n-1}u_{n}$  \> $ a_{0}=\lfloor u_{n-1}/u_{n} \rfloor $ 
\end{tabbing}

Para ejecutar el algoritmo as\'{\i} expresado, en cada iteraci\'on debemos
calcular $a_{i}$, lo que nos cuesta $O(tam(a_{i})tam(u_{i+1}))$ 
operaciones binarias,entonces tenemos un costo total:

\[ O \left( \sum_{0\leq i\leq n-1}{tam(a_{i})tam(u_{i+1})} \right) \]

por otro lado  $v=u_{1}\geq u_{2}\geq u_{3}\geq...\geq u_{n}$ debido a que
$u_{i-2}=a_{i-2}u_{i-1}+u_{i}>u_{i}$, y patiendo del caso base
$u_{0}>u_{1}$ inductivamente vemos que los $u_{i}$ decrecen. Usando esto
obtenemos que:

\[ O \left( \sum_{0\leq i\leq n-1}{tam(u_{i+1})tam(a_{i})} \right) \leq
O \left( tam(v) \sum_{0 \leq\ i \leq n-1}{tam(a_{i})} \right) \]

 Adem\'as, por la definici\'on de la funci\'on $tam$ se tiene que
$tam(a_{i}) \geq 1+ \log{a_{i}}$, con lo que vemos que:

\[O \left( tam(v) \sum_{0 \leq\ i \leq n-1}{tam(a_{i}}) \right)  \leq O
\left( tam(v)(n+ \log{\prod_{0 \leq i \leq n-1}{a_{i}}})  \right) \]

pero $a_{i}=\lfloor u_{i}/u_{i+1} \rfloor$, entonces:

\[ \prod_{0 \leq i \leq n-1}{ \lfloor \frac{u_{i}}{u_{i+1}} \rfloor }  
\leq 
\prod_{0 \leq i \leq n-1}{\frac{u_{i}}{u_{i+1}}} 
=
\frac{u_{0}}{u_{n}} = u \]

entonces 
\[ O  \left( tam(v)(n+ \log{\prod_{0 \leq i \leq n-1}{a_{i}}})  \right) =
 O \left( tam(v)(n+\log{u}) \right) \]

vimos que el numero de iteraciones $n$  es $O(\log{u})$ obteniento
as\'{\i}, que el
algoritmo de
Euclides en la entrada $u,v$ realiza 

  \[ O(tam(v)tam(u)) \] operaciones binarias.
						   
\end{proof}

\begin{proposition}
Sean u,v,c enteros, $au+bv=c$ tiene soluci\'on entera si y s\'olo si 
$mcd(u,v)|c$
\end{proposition} 
\begin{proof}
Si la ecuaci\'on $au+bv=c$ tiene soluci\'on entera para $a$ y $b$,
significa
que al dividir $au+bv$ por $\mcd{u}{v}$ nos resulta un entero, entonces es claro
que $mcd(u,v)|c$.

Para la otra implicancia, usaremos el algoritmo de Euclides,

\[ u_{i-2}=a_{i-2}u_{i-1}+u_{i} \]
reescribiendo
\[ u_{i}=-a_{i-2}u_{i-1}+u_{i-2} \]
\[ u_{i-1}=u_{i-1} \]

podemos escribir estas ecuaciones de forma matricial

\[ \left[ \begin{array}{c}
	 u_{i}\\
	 u_{i-1} 
          \end{array} \right] 
= \left[ \begin{array}{cc}	    
                    -a_{i-2} & 1 \\
		           1 & 0 
       \end{array} \right]
      \left[ \begin{array}{c} 
                         u_{i-1} \\
                         u_{i-2} 
	      \end{array} \right]  \]

As\'{\i} expuesto, comenzamos con el vector
\[ \left[ \begin{array}{c} 
	   u_{0} \\
	   u{1} \end{array} \right] \]   \\

que lo vamos multiplicando en cada paso por una matriz para obtener el
nuevo paso de la iteraci\'on


\[ \left[ \begin{array}{c}
            u_{2} \\
            u_{1} \end{array} \right] 
=
\left[ \begin{array}{cc}
            -a_{0} & 1 \\
            1     & 0 \end{array} \right]
\left[ \begin{array}{c}
            u_{1} \\
            u_{0} \end{array} \right] \]

Al aplicar iterativamente podemos ver

\[ \left[ \begin{array}{c}
                u_{i} \\
                u_{i-1} \end{array} \right]
=
\left[ \begin{array}{cc}
                -a_{i-2} & 1 \\
                    1    & 0 \end{array} \right]
\left[ \begin{array}{cc}
                -a_{i-3} & 1 \\
                    1    & 0 \end{array} \right]
...
\left[ \begin{array}{cc}
                -a_{0} & 1 \\
                   1   & 0  \end{array} \right]
\left[ \begin{array}{c}
                   u_{1} \\
                   u_{0}  \end{array} \right] \]



como sabemos que al terminar el algoritmo $u_{n}=0$ y $u_{n-1}=mcd(u,v)=d$
,al 
final del producto de matrices nos queda:

\[ \left[ \begin{array}{c}
	 0\\
	 d
         \end{array} \right]
= \left[ \begin{array}{cc}
                          m_{11} & m_{12} \\
                          m_{21} & m_{22}
          \end{array} \right] 
 \left[ \begin{array}{c}
                          u \\
                          v
           \end{array}
                      \right] \]

donde la matriz $M=m_{ij}$ es la multiplicaci\'on de las matrices
obtenidas en cada iteraci\'on, y todos sus elementos son enteros.

Entonces, $d=m_{11}u+m_{12}v$   es decir, existen $a$ y $b$ que cumplen
$d=au+bv$, y $d=\mcd{u}{v}$.

\end{proof}

Notemos que esta demostraci\'on nos da un m\'etodo para calcular los
coeficientes 
$a$ y $b$.

Decimos que dos enteros $a$ y $b$ son \emph{primos relativos} si
  $\mcd{a}{b}=1$, i.e. si no tienen divisores comunes mayores que $1$.
\begin{corollary}\label{cor:euclid}
Si $a$ y $b$ son primos relativos, entonces existen enteros $u$ y $v$
  tales que $1=u\,a+v\,b$.
\end{corollary}

Basandonos en la  demostraci\'on anterior , veremos un nuevo m\'etodo:

\section{El algoritmo de Euclides extendido}

El algoritmo es el siguiente:

\begin{tabbing}
lllllllllllllllllllll\=llll\=llll\=       \kill
\>$EucludEx(u,v)$ \\
\>\> $M \leftarrow \left[ \begin{array}{cc} 1 & 0 \\ 0 & 1 
		      \end{array}  \right]$ \\
\>\> $n \leftarrow 0$ \\
\>\> while (v$\neq $0) do \\
    \>\>\>$q\leftarrow \lfloor \frac{u}{v} \rfloor$ \\
    \>\>\>$M \leftarrow M \left[ \begin{array}{cc} q & 1 \\ 1 & 0
                      \end{array}  \right] $ \\
    \>\>\>$(u,v)\leftarrow (v,u-qv)$ \\
    \>\>\>$n \leftarrow n+1$\\
\>\>return($d=u,a=(-1)^{n} M_{22},b=(-1)^{n+1} M_{12}$)\\
\>end:\\
\end{tabbing}

Este algoritmo, adem\'as de retornar el \emph{m\'aximo com\'un divisor} de
$u$ y $v$, nos retorna las constantea $a$ y $b$ que cumplen con la
ecuaci\'on $au+bv=mcd(u,v)$.  


\end{document}



