Algoritmos aritméticos (13 min)

El próximo tema que trataremos, es como usar la aritmética modular de grandes enteros.

La primera pregunta es como representar grandes enteros en un ordenador,

Eso resulta relatívamente simple. Imaginemos que estamos en una máquina de 64 bits,

lo que haríamos es separar el número que queremos representar en bloques de 32 bits.

Y básicamente tendríamos N en bloques de 32 bits que juntos

representan el número que queremos almacenar en el ordenador. Debo mencionar

que estoy usando 64 bits como ejemplo. De hecho, muchos procesadores

modernos tienen registros de 128 bits o más, y podemos incluso hacer multiplicaciones con ellos.

Así que normalmente, usaríamos bloques mucho mayores de 32 bits.

La razón por la que quremos limitarnos a 32 bits, es para poder multiplicar

2 bloques, ya que el resultado será menor de 64 bits,

menor que el tamaño de palabra de la máquina. Veamos ahora algunas operaciones

aritméticas y veamos el tiempo que precisan. La suma y la resta

básicamente usarían el acarreo para la suma y el préstamo

para la resta, y son básicamente operaciones de tiempo lineal. En otras palabras,

si sumamos o restamos 2 enteros de tamaño N, el tiempo necesario es básicamente

lineal en N. La multiplicación mas simple precisará un tiempo cuadrático. De hecho

es lo que se conoce por el algorítmo "del instituto". Es aproximadamente lo

que aprendimos en la escuela, y si pensamos un minuto, veremos

que el algoritmo es básicamente cuadrático en relación a la longitud de los números que estamos

multiplicando. Una gran sorpresa en los años 60 fué el algoritmo de Karatsuba que

consigue resultado mucho mejor que tiempo cuadrático. De hecho, consiguió

un tiempo de n elevado a 1,585. No es realmente interesante enseñar

como funciona exactamente el algoritmo, y por tanto mostraré solo la idea principal. Lo que

Karatsuba advirtió es que para multiplicar 2 números podemos

tomar el primer número X, y escribirlo como 2 elevado a B por X2 más X1.

Donde X2 y X1 son del tamaño aproximado de la raiz de X. Así que

podemos separar el número X en parte izquierda de Z y parte derecha de X.

Y básicamente, escribimos X como si estuviera escrito en base 2 a la b. Eso son

dos dígitos en base 2 a la b. Y se hace los mismo con y. Se escribe y en base

2 a la b. Una vez más, se debería escribir como la suma de la mitad izquierda más la

mitad derecha, y luego, normalmente, si se intenta hacer esta multiplicación, al desplegar

los paréntesis se ve que esto requeriría 4 multiplicaciones.

Requeriría x2 por y2, x2 por y1, x1 por y2 y x1 por y1.

Karatsuba se dio cuenta de que hay una manera de hacer esta multiplicación de x por y usando sólo

tres multiplicaciones de x1 x2 y1 y2, por lo que una gran multiplicación de x por y

sólo necesita tres pequeñas multiplicaciones. Ahora, recursivamente, se puede

aplicar exactamente el mismo procedimiento para multiplicar x2 por y2 y x2 por y1,

y así sucesivamente, y se obtiene este algoritmo recursivo. Y si se hace un

análisis recursivo, se verá que básicamente, se consigue un tiempo de ejecución de n elevado a 1,585.

Este número 1,585 es, básicamente, el logaritmo de 3 en base 2.

Sorprendentemente, resulta que Karatsuba no es el mejor algoritmo de

multiplicación que existe. De hecho, se puede multiplicar en un tiempo

aproximadamente n*log n, por tanto en tiempo casi lineal. Sin embargo, este es

un resultado extremadamente asintótico. La O esconde constantes muy grandes. Y por

tanto, el algoritmo solo es práctico cuando los números son absolutamente

enormes. Por tanto el algoritmo no se usa muy a menudo. Pero

el algoritmo Karatsuba es muy práctico, y de hecho, la mayoria de librerías de criptografia

lo implementan para la multiplicación. Sin embargo, para simplificar

voy a ignorar el algoritmo de Karatsuba y por simplicidad, voy a

asumir que la multiplicación se ejecuta en tiempo cuadrático. Pero debemos recordar

siempre que la multiplicación es algo más rápida

que cuadrática. Y la siguiente pregunta después de la multiplicación

es sobre la división con resto, que resulta ser también un algoritmo cuadrático. Así que la

operación principal que nos queda, y que hemos usado muchas veces hasta el momento,

y que nunca he explicado como calcular es

la exponenciación. Vamos pués a resolver el problema de la exponenciacón

de un modo abstracto. Imaginemos que tenemos un grupo cíclico G. Esto significa que este

grupo es generado de las potencias de un generador g minúscula. Por ejemplo

imaginemos un grupo Zp estrella, y supongamos que g minúscula es un generador de G mayúscula.

La razón de establecer esto de esta manera es que quiero que se empiece a utilizar

esta abstracción donde tratamos con un grupo genérico g y ZP que es realmente

un ejemplo de dicho grupo. Pero, de hecho, hay muchos otros ejemplos de

grupos cíclicos finitos. Y una vez más quiero enfatizar básicamente que el grupo G

simplemente es el conjunto de potencias del generador hasta el orden del grupo.

Voy a escribirlo como g elevado a q. Así que nuestra meta ahora es, dado este elemento g y algún

exponente x, nuestro objetivo es calcular el valor de g a la x. Ahora normalmente lo que

podría decirse que se podría pensar, si x es igual a 3, entonces voy

a calcular g elevado al cubo. Bueno, realmente hay nada que hacer. Todo lo que hago es

g por g por g y obtengo g elevado al cubo, que es lo que quería. Por lo que

en realidad es bastante fácil. sin embargo, este no es el caso que nos interesa. En

nuestro caso, nuestros exponentes van a ser enormes. Y por tanto si

suponemos un número 500 bits, si se intenta calcular g elevado a un

número de 500 bits, simplemente multiplicando g por g por g por g esto va a tomar bastante tiempo.

De hecho llevará tiempo exponencial que no es algo que interese

hacer. Así que la pregunta es si a pesar de que x es enorme, podemos aún calcular

g elevado a x relativamente rápido, y la respuesta es sí y el algoritmo que lo hace

se llama un algoritmo cuadrado repetitivo.
Así que permítanme explicar cómo funciona

el algoritmo cuadrado repetitivo. Vamos a tomar como ejemplo, 53. Ingenuamente tendrían que hacer

53 multiplicaciones de g por g por g por g hasta llegar a g por el 53 pero quiero

mostrarles cómo puede hacerse muy rápidamente.
Por tanto lo que haremos es escribiremos 53

binario. Se trata de la representación binaria de 53 y todo lo que implica.

Nótese que este corresponde a 32, este a dieciséis, éste

corresponde a cuatro, y éste corresponde a uno. Así que realmente 53 es 32

más 16 más 4 más 1. Pero lo que esto significa es que g a la potencia 53

es g elevado a 32+16+4+1. Y lo podemos desglosar, una vez más, utilizando las reglas de

exponenciación. Podemos desglosarlo como g elevado a 32 por g elevado a 16 por

g elevado a 4 por g elevado a 1. Esto debería dar una idea de cómo calcular muy rápidamente

g elevado a 53. Lo que haremos es, simplemente, tomamos g y empezamos

a elevarlo al cuadrado. Así obtenemos g cuadrado. Elevamos de nuevo al cuadrado todo lo necesario

obteniendo g elevado a 4, g elevado a 8, g elevado a 16 y g elevado a 32. Por tanto

hemos calculado todas estos cuadrados de g. Y ahora, simplemente vamos a

multiplicar las potencias apropiadas para obtener g elevado a 53.

Así, g elevado a uno por g elevado a 4 por g elevado a 16 por g elevado a 32, básicamente

va a darnos el valor que queremos, que es g elevado a 53. Aquí vemos que

simplemente tuvimos que calcular, tuvimos que hacer uno, dos, tres, cuatro,

cinco cuadrados, además de cuatro multiplicaciones. Así, con 9 multiplicaciones calculamos

g elevado a 53. Esto es bastante interesante. Y resulta que esto es un

fenómenos general que nos permite elevar g a potencias muy altas y hacerlo muy

rápidamente. Así que permítanme mostrarles el algoritmo. Como ya he dicho, esto se llama algoritmo del cuadrado repetido

Así, la entrada al algoritmo es el elemento g y el

exponente x. Y el resultado es g elevado a x.
Así que lo que vamos a hacer es

escribir x en notación binaria. Vamos a decir que x tiene n bits. Y esta es la

representación real en bits de x como un número binario. Entonces haremos lo

siguiente: Tendremos estos dos registros:
y va a ser un registro constantemente

elevado al cuadrado. Y z va a ser un acumulador que se multiplica en las

potencias apropiadas de g según sea necesario. Así, lo que haremos es lo siguiente: recorreremos los

bits de x comenzando por los bits menos significativos, y a continuación, hacemos lo

siguiente: en cada iteración simplemente elevamos al cuadrado y. Bien, sólo

elevar al cuadrado en cada iteración. Y entonces, siempre que el correspondiente bit del

exponente x sea uno, simplemente acumulamos el valor de y en

este acumulador z, y al final, simplemente entregamos z. Eso es todo. Eso es

el algoritmo completo, y eso es el algoritmo del cuadrado repetido. Así, vamos a ver un

ejemplo con g elevado a 53. Se pueden ver las dos columnas. y es una

columna, que evoluciona a durante las iteraciones y z es otra columna, que de nuevo

evoluciona durante las iteraciones. Así, y no es muy interesante. Básicamente, todo

lo que le ocurre a y es que en cada iteración, simplemente se obtiene su cuadrado. Y así

sólo recorre las potencias de dos y los exponentes, y eso es todo. z es

un registro más interesante que acumula

las potencias adecuadas de g cuando el bit correspondiente al exponente es uno. Así, por ejemplo,

el primer bit del exponente es uno, por tanto, al final de la primera

iteración el valor z es simplemente igual a g. El segundo bit del exponente es cero

por lo que el valor de z no cambia después de la segunda iteración. Y al final de la

tercera iteración el tercer bit del exponente es uno, así acumulamos g elevado

a 4 en z. El siguiente bit del exponente es cero, por lo que z no cambia. El

siguiente bit del exponente es uno. Ahora suponemos que se acumula el anterior

valor de y en el acumulador z así que permítame preguntar cual va a ser el valor de z?

Bueno, simplemente acumulamos g elevado a 16 en z, simplemente calculamos la suma

de 16 y 5 y obtenemos g elevado a 21.
Finalmente, el último bit se establece también en uno

por lo que se acumula en z, hacemos 32 más 21 y conseguimos finalmente como salida g elevado a 53.

Muy bien, esto nos da una idea de cómo funciona el algoritmo del cuadrado repetido.

Es es un algorism interesante y nos permite calcular potencias enormes de

g muy, muy, muy rápidamente. Por lo que el número de iteraciones, esencialmente, sería

el logaritmo en base 2 de x. Bien. Tenga en cuenta que el número de iteraciones depende simplemente del

número de dígitos de x, que es básicamente el logaritmo en base 2 de x. Así que incluso si x es un

número de 500 bits, en 500 multiplicaciones -bueno, 500 iteraciones, realmente 1.000

multiplicaciones, porque tenemos que elevar al cuadrado y acumular-. En 1.000

multiplicaciones podremos plantear g elevado a la potencia de un exponente de 500 bits.

Vale ahora podemos analizar el tiempo de ejecución. Supongamos

que tenemos un módulo de N bits como N mayúscula. Como dijimos, la suma y la resta de ZN consume un

tiempo lineal. La multiplicación, como he dicho, Karatsuba la hace

más eficientemente, y por simplicidad sólo decimos que consume un tiempo cuadrático. Y la

exponenciación, como he dicho, básicamente consume logaritmo de x repeticiones, y en cada

iteración básicamente hacemos dos multiplicaciones. Por tanto, es O (log (x))

veces el tiempo para multiplicar. Y vamos a decir que el tiempo para multiplicar es cuadrático. Por lo tanto

el tiempo de ejecución sería, realmente, N cuadrado logaritmo de x. Y dado que x es siempre

inferior a N, por el teorema de Fermat, no hay ningún punto elevando g a una potencia

que sea mayor que el módulo. Así x será menor que N. Supongamos que x

también es un entero de n bits. Entonces, la exponenciación es realmente un algoritmo de tiempo cúbico.

Está bien, eso es lo que quería recordar, la exponenciación es realmente

relativamente lenta. Actualmente, realmente tarda unos microsegundos en un

ordenador moderno. Pero incluso microsegundos para -digamos- un procesador de cuatro gigahercios es

un poco de trabajo. Y sólo tenga en cuenta que en toda la exponenciación

hablamos de operaciones. Por ejemplo, para determinar si un número es un

residuo cuadrático o no, toda esa exponenciación básicamente consume un tiempo cúbico.

Muy bien, así terminé nuestra discusión de algoritmos aritméticos y luego en el

segmento siguiente comenzaremos hablando sobre problemas difíciles, módulo, números primos y compuestos.