\documentclass{article}

\usepackage{amssymb}

\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{proof}{\noindent\par{\bf Dem:}\ }{\(\qed\) \par\medskip}
%\newenvironment{dem}{\startproof}{\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

\newcommand{\ie}{{\em i.e.}}
\newcommand{\plain}{{\cal P}}
\newcommand{\cipher}{{\cal C}}
\newcommand{\key}{{\cal K}}
\newcommand{\encrip}{{\cal E}}
\newcommand{\decrip}{{\cal D}}

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

\newcommand{\chapref}[1]{\mbox{Capitulo~\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}}}


\begin{document}

% LOS DATOS IDENTIFICATORIOS DE LA CATEDRA TRANSCRITA VAN AQUI
% (modificar los parametros en invocacion de la siguiente macro:
%	primer parametro: No. de catedra transcrita
%	segundo parametro: fecha de catedra transcrita
%	tercer parametro: Nombre del transcriptor

% En caso que la transcripcion no este basada en una transcripcion de
% an~os anteriores usar:
\catedra{4}{24 de Marzo}{Cristian Bravo L.}

% En caso que la transcripcion ESTE basada en una transcripcion de 
% an~os anteriores usar: 
%\catedra{1}{16 de Marzo}{Marcos Kiwi\footnotemark}
%\footnotetext{Estos apuntes est\'an basados en la transcripci\'on de Marcos Kiwi (6/8/96)}

% TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI

\section{Algoritmo de Euclides Extendido}

Recordemos de la c\'atedra anterior que es posible expresar la secuencia
de ecuaciones del algoritmo de Euclides en forma matricial (forma que
llamamos \emph{algoritmo extendido}). Ello nos permite encontrar, dados
dos enteros $u$ y $v$, las soluciones enteras de la ecuaci\'on
$\mcd{u}{v}=au+bv$. Este detalle tiene bastante importancia pr\'actica,
como veremos a continuaci\'on. \\

Uno de los problemas planteados en c\'atedras anteriores consiste en
calcular el inverso multiplicativo de un elemento $q$ dado en el conjunto
$\modulo_{m}$. Como sabemos que este inverso existe si y s\'olo si $q$ y
$m$ son primos relativos (es decir, si $\mcd{q}{m}=1$), conocemos un
m\'etodo para calcular este inverso, de la siguiente forma :
%
\begin{eqnarray*}
aq+bm=1 & \Leftrightarrow & [aq+bm](\mathrm{mod}\,m)=[aq]=[a][q]=[1] \\
	& \Leftrightarrow & aq \equiv 1 (mod m) \\
        & \Leftrightarrow & q^{-1} \equiv a (\mathrm{mod}\,m) \\
\end{eqnarray*}
Nos interesa saber si este c\'alculo puede llevarse a cabo en forma
eficiente. En una c\'atedra anterior se prob\'o que el
algoritmo de Euclides requiere $O(\log u \log v)$ operaciones binarias,
resultado que tambien es cierto para el algoritmo de Euclides extendido.
Luego, basados en el resultado anterior, es posible determinar el inverso
de un elemento $q\in\modulo_{m}$ en $O(\log q \log m)$ operaciones
binarias.

No obstante, a\'un no sabemos nada acerca de la complejidad real de las
operaciones b\'asicas. Es decir, si implement\'asemos el algoritmo extendido
de Euclides en un computador tenemos una idea aproximada acerca del
n\'umero de multiplicaciones y sumas que realizar\'{\i}a, pero no sabemos
cu\'antas operaciones tiene que llevar a cabo un computador para dividir
dos enteros, por ejemplo.

En la siguiente secci\'on estudiaremos la complejidad de las operaciones
b\'asicas: suma, resta, multiplicaci\'on, divisi\'on y mod (es decir,
resto de una divisi\'on entera).

\section{Complejidad de Operaciones B\'asicas.}

\subsection{Suma}

B\'asicamente, el algoritmo para sumar dos n\'umeros binarios es el mismo
que usamos desde ni\~nos en la escuela, s\'olo que nos interesa, por
motivos de implementaci\'on computacional, representar los n\'umeros en
notaci\'on binaria. Tomemos dos enteros $x$ e $y$, y representemos por $z$
el resultado de su suma. La operaci\'on podr\'{\i}amos esquematizarla como
sigue:

\begin{displaymath} \begin{array}{c}
x=x_{l-1}\ldots x_0 \\ y=\underline{y_{l-1}\ldots y_0} \\
\quad z_l\,z_{l-1}\ldots z_0\\
\end{array} \end{displaymath}
donde $x_i,\,y_i\in\{0,1\}$, $z_i=(x_i+y_i+c_i)\mathrm{mod}\,2$,
y $c_{i+1}=\lfloor\frac{x_i+y_i+c_i}{2}\rfloor$, $i\geq 0$.

Ahora bien: para $i=0$, $c_1=\lfloor\frac{x_0+y_0+c_0}{2}\rfloor$, donde
$c_0=0$, por lo que $c_1\in \{0,1\}$. Supongamos ahora que
$c_i\in\{0,1\}$. Esto nos lleva a que el m\'{\i}nimo valor que puede tomar
$c_{i+1}$ es $0$, pues $\lfloor\frac{0+0+0}{2}\rfloor=0$; a su vez, el
m\'aximo valor que puede tomar $c_{i+1}$ es 1, pues
$\lfloor\frac{1+1+1}{2}\rfloor=1$. Luego, $c_i\in\{0,1\},\,i\geq 0$; es
decir, $c_i$ es un bit. Tradicionalmente, a \'este \'ultimo se le llama
\emph{de acarreo}, pues representa el \emph{desborde o acarreo} que
tenemos que hacer de un grupo de n\'umeros al siguiente. 

Observando que $|c_i|\leq 1$, se concluye que, para sumar $x$ e $y$,
debemos hacer l+1 operaciones binarias de $O(1)$ cada una. Es decir,
el costo total de sumar dos enteros es $O(l)$, donde $l$ es el largo de la
representaci\'on binaria del mayor de ambos n\'umeros.

\subsection{Multiplicaci\'on}

Nuevamente, el algoritmo usado aqu\'{\i} es id\'entico al que usamos
manualmente, s\'olo que aplicado a n\'umeros binarios. Supongamos dos
enteros $x$ e $y$, cuyas representaciones binarias tienen largos $l$ y
$t$, respectivamente. Supongamos, sin perder generalidad, que $t<l$.
Podemos esquematizar la operaci\'on de multiplicaci\'on como sigue:
\begin{center} \begin{tabular}{rrrrrrr}
 & & $x\quad=$ & $x_{l-1}\qquad$ & \ldots & $x_0$\\
 & & $y\quad=$ & $\qquad y_{t-1}$ & \ldots & $y_0$\\
\put(90,20){\line(1,0){100}}
 & & & $z_{0,l-1}$ & \ldots & $z_{0,0}$ \\
 & & $z_{1,l-1}$ & \ldots & $z_{1,0}$ & \\
 & \ldots & & \ldots & & \\
$z_{t-1,l-1}$ & \ldots & $z_{t-1,0}$ & & & \\ \hline
$w_{t+l-1}$ & $w_{t+l-2}$ & & \ldots & & $w_0$ \\
\end{tabular} \end{center}

donde $z_{i,j}=y_i x_j$,
$w_r=\left(\sum_{i+j=r}z_{i,j}+c_r\right)\,\mathrm{mod}\,2$ y
$c_{r+1}=\left\lfloor\frac{\sum_{i+j=r}z_{i,j}+c_r}{2}\right\rfloor$. 

Aqu\'{\i} el $c_r$ \textbf{no es} necesariamente un bit, pero se
corresponde con la misma idea que el \emph{bit de acarreo} en las
f\'ormulas de la suma:  es el \emph{desborde} que resulta de sumar una
tupla de bits.

El algoritmo es como sigue : se toma cada d\'{\i}gito de $x$, y se va
multiplicando por $y_0$, obteniendo una tupla de bits $z_{0,l-1}\cdots
z_{0,0}$, que es igual a $x$ si $y_{0}=1$ \'o igual a 0 si $y_0=0$. Se
repite la operaci\'on para todos los d\'{\i}gitos de $y$ ($y_1, y_2$,
etc.), y se van obteniendo sucesivas cifras binarias, que vamos
desplazando en un bit cada vez (ver figura). Finalmente se suman todas
estas cifras.

Del an\'alisis anterior podemos darnos cuenta de que estamos realizando
$lt$ multiplicaciones de pares de bits, y $t+l$ sumas de a lo m\'as $t$
bits. Esto \'ultimo puede ampliarse diciendo que estamos haciendo a lo
m\'as $(t+l)(t)=t^2+lt$ operaciones, es decir, $O(t^2+lt)=O(lt)$, pues
$t<l$.  Finalmente, el multiplicar dos enteros de $l$ y $t$ bits de largo,
lleva $O(lt+lt)=O(lt)$ operaciones binarias el ser llevada a cabo. 

Como $O(lt)$ es un n\'umero relativamente grande de operaciones binarias
por hacer, surge naturalmente una pregunta: > Existe un algoritmo m\'as
r\'apido que permita multiplicar dos enteros ? La respuesta es s\'{\i}, se
han descubierto varios algoritmos para multiplicar enteros mejores que el
descrito m\'as arriba. Sin embargo, el problema de determinar el orden
exacto de operaciones binarias que requiere una multiplicaci\'on sigue
siendo un problema abierto.

Veamos uno de estos m\'etodos, sugerido por Katsuba y Ofman en 1962
\footnote{A. Karatsuba, \emph{Doklady Akademiia Nauk} SSSR \textbf{145}
(1962), 293-294.}.

Sean dos enteros $x$ e $y$, ambos representables en $l$ bits. Supongamos,
por comodidad, que $l$ es una potencia de dos. Sean finalmente
$x_0, y_0, x_1, y_1 \in \{0,\ldots,2^{l/2}-1\}$ tales que:
\[ x=x_1 2^{l/2}+x_0=(x_1 x_0)_{2^{l/2}} \]
\[ y=y_1 2^{l/2}+y_0=(y_1 y_0)_{2^{l/2}} \]

En general es posible hacer esto, puesto que $l$ es potencia de dos. 
Cuando representamos $x_i$ e $y_i, i\in\{0,1\}$ en notaci\'on binaria, es
muy f\'acil determinar estos \'ultimos: si \emph{cortamos} la
representaci\'on binaria de $x$ en dos \emph{trozos} de igual cantidad de
d\'{\i}gitos, entonces el \emph{trozo} de la izquierda ser\'a $x_1$ y el
de la derecha ser\'a $x_0$; y de igual forma se obtienen $y_1$ e $y_0$. 
La notaci\'on empleada en las igualdades de la derecha significa
que podemos representar $x$ e $y$ como n\'umeros de dos d\'{\i}gitos,
en base $2^{l/2}$, donde $x_i$ e $y_i$ son estos d\'{\i}gitos.

En la pr\'actica obtener $x_1$, $x_0$, $y_1$ e $y_0$ es muy r\'apido si lo
implementamos a nivel de hardware, pues estamos haciendo un \emph{shift}
hacia la izquierda de $l/2$ bits. El producto de ambos n\'umeros es:

\[ xy=(\underbrace{x_1 y_1}_{z_1})2^l +
(\underbrace{x_1 y_0 + x_0 y_1}_{z_2})2^{l/2} + 
\underbrace{x_0 y_0}_{z_3} \]

Llamemos en la expresi\'on anterior $z_1=x_1 y_1$, $z_2=x_1 y_0 + x_0 y_1$
y $z_3=x_0 y_0$. Podemos relacionar estas nuevas variables a trav\'es de la
siguiente expresi\'on:

\[ z_2=(x_0 + x_1)(y_0 + y_1) - z_1 - z_3 \]

Luego, b\'asicamente estamos calculando $xy$ al precio de 3
multiplicaciones: dos para $z_1$ y $z_3$, y una tercera para $z_2$,
adem\'as de unas cuantas sumas.

Analicemos la cantidad de operaciones binarias necesarias para llegar a
determinar $xy$, a partir de las ecuaciones de m\'as arriba.

Como tomamos la representaci\'on binaria de $x$ y la \emph{cortamos} en
dos trozos del mismo n\'umero de d\'{\i}gitos binarios, entonces la
representaci\'on binaria de $x_0$ e $x_1$ tienen la mitad del largo que la
de $x$ (y an\'alogamente con $y$). Luego, las multiplicaciones
involucradas en el c\'alculo de las tres cantidades anteriores ($z_0, z_1,
z_2$) se realizar\'an sobre enteros de $l/2$ bits de largo. Estas
operaciones consumen la mayor parte del tiempo que le lleva al algoritmo
hacer el c\'alculo de $xy$, pero adem\'as son necesarias dos operaciones
de \emph{shifting} sobre enteros de largo $l/2$, m\'as un n\'umero
constante de operaciones de suma de enteros de a lo m\'as $l$ bits; ambas
operaciones se realizan en un tiempo proporcional a $l$, por lo que en el
an\'alisis que haremos a continuaci\'on, representamos estas operaciones
como un factor constante ($c$) por $l$. 

Si $T(l)$ es el tiempo que necesitamos para encontrar $xy$, entonces:
\begin{eqnarray*}
T(l) & \leq & 3T(\frac{l}{2}) + cl \\
     & \leq & 3(3T(\frac{l}{4}) + \frac{cl}{2}) + cl = 9T(\frac{l}{4}) + \frac{3}{2}cl + cl\\
     & \leq & 27T(\frac{l}{8}) + \frac{9}{4}cl + \frac{3}{2}cl + cl \\
     & \leq & \cdots\\
     & \leq & cl\left(1+(\frac{3}{2})+(\frac{3}{2})^2+\ldots+(\frac{3}{2})^{\log_2 l-1}\right)+ 3^{\log_2l}T(1) \\
     & = & 2cl\left(\frac{\frac{3^{\log_2l-1}}{2}-1}{\frac{3}{2}-1}\right)+3^{\log_2l}T(1)\\
     & \leq & (2c+T(1)) l^{\log_23} = O(l^{\log_23}) 
\end{eqnarray*}

Con lo anterior, podemos mejorar el tiempo de ejecuci\'on del algoritmo
cl\'asico de multiplicaci\'on de $O(n^2)$ a $O(n^{1,585...})$.

Una vez que uno ha entendido el algoritmo anterior, es natural preguntarse
si es posible generalizarlo, en el sentido de dividirlo en un n\'umero
mayor de \emph{trozos} (m\'as que dos). En general es posible hacerlo,
siempre que se multipliquen enteros suficientemente grandes. 

Supongamos ahora que tenemos $x$ e $y$, representables ambos en $(r+1)n$
bits:
\[u=(u_{(r+1)n-1}\cdots u_1u_0)_2,\qquad v=(v_{(r+1)n-1}\cdots v_1v_0)_2\]
donde la notaci\'on anterior significa que ambos n\'umeros est\'an en
notaci\'on binaria.  Ambos pueden \emph{dividirse} en $r+1$ \emph{trozos},
de manera que queden de la siguiente forma: 
\[u=U_r2^{nr}+\cdots+U_12^{n}+U_0,\qquad
v=V_r2^{nr}+\cdots+V_12^{n}+V_0\]
donde cada $U_i$ y $V_i$ son n\'umeros de $n$ bits de largo. Consideremos
los siguientes polinomios:
\[ U(x)=U_rx^r+\cdots+U_1x+U_0, \qquad V(x)=V_rx^r+\cdots+V_1x+V_0, \]

\newpage y sea
\[W(x)=U(x)V(x)=W_{2r}x^{2r}+\cdots+W_1x+W_0.\]
Ya que $u=U(2^n)$ y $v=V(2^n)$, se cumple que $uv=W(2^n)$, as\'{\i} que
podemos calcular $uv$ si conocemos los coeficientes de $W(x)$. El problema
que antes resolvimos definiendo tres constantes, se ampl\'{\i}a ahora a
encontrar una buena forma de calcular estos coeficientes. Esto no es
dif\'{\i}cil: basta con calcular $W_0, W_1, \ldots$ en orden:
\[U(0)V(0)=W(0)=W_0,\qquad U(1)V(1)=W(1)=W_{2r}+\cdots+W_1+W_0,\qquad
\mathrm{etc.}\]

\subsection{Divisi\'on}

La divisi\'on es bastante m\'as complicada de realizar que la
multiplicaci\'on. Sean nuevamente dos enteros $u$ y $v$, de largos
binarios $l$. La idea general es la siguiente : para calcular
$q=\lfloor\frac{u}{v}\rfloor$, basta con calcular $\frac{1}{v}$ con
suficiente precisi\'on y luego multiplicar ambas cantidades. Para que la
divisi\'on sea satisfactoria, necesitamos $l$ bits de precisi\'on, es
decir, necesitamos precisi\'on $\frac{c}{2^{l+1}}$, donde $c=O(1)$, pues
si obtenemos w tal que:

\[ \left|w-\frac{1}{v}\right|\leq \frac{c}{2^{l+1}} \]
entonces
\[ \Rightarrow \left|uw-\frac{u}{v}\right|\leq c\frac{u}{2^{l+1}} <c \]

pues $u$ tiene $l$ bits, u es a lo m\'as $2^{l}-1$; llamemos $\hat{q}=uw$ y
desarrollemos el valor absoluto:

\[ -c+q \leq -c+\frac{u}{v} < \hat{q} < c+\frac{u}{v} \leq c+q+1 \]
\[ \Rightarrow q\in [\hat{q}-c-1, \hat{q}+c] = \mathbf{I} \]

Luego, basta probar con todos los $q\in\mathbf{I}$ hasta dar con una
aproximaci\'on suficientemente buena, tal que:

\[ 0\leq \underbrace{u-qv}_{u\,\mathrm{mod}\,v}<v \]

Ahora bien: no hemos dicho nada acerca de c\'omo calcular $1/v$. La idea es
usar el m\'etodo de Newton para resolver $f(x)=\frac{1}{v}-x=0$, lo que
converge cuadr\'aticamente y, por lo tanto, no debiera darnos una mala
cota para el tiempo total de la operaci\'on.

Iteramos entonces sobre $x_{n+1}=2x_n-vx_n^2$ con un $x_0$ elegido
adecuadamente (?) y obtenemos $\lfloor\frac{1}{v}\rfloor$. Veremos a
continuaci\'on, sin \'animo de an\'alisis, un algoritmo descrito en
\emph{seudoc\'odigo}, que permite calcular esta \'ultima cantidad.

\newpage \texttt{Inverso($v$)}\\\{
\begin{flushleft}
$\quad x\longleftarrow\frac{1}{4}\left\lfloor\frac{32}{4v_1+2v_2+v_3}\right\rfloor$\\
$\quad k \longleftarrow 0$\\
$\quad \mathrm{while}\,(2^k<l)\,\mathrm{do}$\\
$\qquad\qquad v_k\longleftarrow(0.v_1\ldots v_{2^{k+1}+3})_2$\\
$\qquad\qquad x\longleftarrow\frac{1}{2^{2^{k+1}}+1}\lfloor2^{2^{k+1}}+1(2x-v_k x^2)\rfloor$\\
$\qquad\qquad k\longleftarrow k+1$\\
$\quad return(x)$ \\ \}
\end{flushleft}

Se puede probar que $x\leq 2$ y $\left|x-\frac{1}{v}\right|\leq 2^{-2^k}$
al comienzo y al final del \emph{while}. Luego,
\[ \mathrm{\# op.bin.}\, = (2T(2l)+cl)+ (2T(l)+cl/2) + (2T(l/2)+cl/4) +
\ldots + (2T(2)+c) \leq O(l^{\log_23}) \]

de lo que concluimos que $T(n)=O(n^{\log_23})$. Un an\'alisis m\'as
riguroso permitir\'{\i}a concluir que para calcular
$q=\lfloor\frac{u}{v}\rfloor$, se requieren $O(\log u \log v)$ operaciones
binarias, lo que hace equivalentes la divisi\'on y la multiplicaci\'on en
t\'erminos de costo de c\'alculo.

\subsection{Resta y M\'odulo}

No es necesario un gran an\'alisis para notar que la resta posee el mismo
costo que la suma, con igual tama\~no de entrada.

Con respecto al m\'odulo el an\'alisis no es tampoco demasiado complejo. 
Sean $u,v>0$ enteros de $l$ bits de largo. Calcular
$u\,\mathrm{mod}\,v=u-\lfloor\frac{u}{v}\rfloor v$ cuesta esencialmente lo
mismo que una divisi\'on y una multiplicaci\'on de n\'umeros de $l$ bits
de largo, as\'{\i} que esta es la operaci\'on m\'as costosa de todas las
que hemos visto.

\end{document}



