Exponenciación binaria

Exponenciación binaria

Exponenciación binaria

La exponenciación binaria es un algoritmo utilizado para calcular de forma rápida grandes potencias enteras de un número x dado. También es conocido como potenciación por cuadrados o elevar al cuadrado y multiplicar. Implícitamente utiliza la expansión binaria del exponente. Es de uso bastante regular en aritmética modular. Este algoritmo es similar al de la duplicación en la multiplicación.

Contenido

Versión recurrente

Fundamentos

El algoritmo está basado en las siguientes tres propiedades de la potencia:

(1) x^1=x\,

(2) x^{a+b}=x^a\,x^b

(3) x^{a\,b}=\left(x^a\right)^b

Usando a = n − 1 y b = 1 en la ecuación (2) se sigue que x^n=x^{n-1}\,x. Tomando \textstyle a=\frac n 2 y b = 2 en la ecuación (3) se obtiene que x^n=\left(x^\frac n 2\right)^2.

Algoritmo

El siguiente algoritmo recursivo calcula xn para un natural n dado:

x^n=\begin{cases} x & \mbox{si }n=1 \\ \left(x^{\frac n 2}\right)^2 & \mbox{si }n\mbox{ es par} \\ x\times x^{n-1} & \mbox{si }n\mbox{ es impar} \end{cases}

Comparado con el método original de multiplicar x por sí mismo n − 1 veces, este algoritmo sólo utiliza O(log n) multiplicaciones y acelera el cálculo de xn tremendamente; más o menos de la misma forma que el algoritmo de la multiplicación acelera una multiplicación sobre el método más lento de realizar una suma repetida.

Aplicaciones

La misma idea permite el cálculo rápido de potencias muy grandes en módulo. Especialmente en criptografía, es útil calcular potencias en el anillo de los enteros módulo q.

La idea puede ser usada también para computar potencias de números enteros en un semigrupo, usando la regla

Potencia(x, -n) = (Potencia(x, n))-1.

Este método funciona en cualquier semigrupo, y es usado frecuentemente para calcular potencias de matrices.

Por ejemplo, la evaluación de

13789722341 (mod 2345)

tomaría mucho tiempo y espacio de almacenamiento si el método ingenuo es usado: calcular 13789722341 y tomar el residuio cuando es dividido por 2345. Incluso usando un método más efectivo tomará tiempo considerable: elevar 13789 al cuadrado , tomar el residuo cuando se divide por 2345, multiplicar el resultado por 13789, y así sucesivamente. Este proceso realizará 722340 multplicaciones modulares. Este algoritmo está basado en la observación que 13789722341 = 13789(137892)361170. Entonces, si se calcula 137892, el cálculo completo tomaría 361170 multiplicaciones modulares. Ésta es una ganacia en un factor de dos. Pero como el nuevo problema sigue siendo similar al anterior, se puede aplicar al observación nuevamente, reduciendo a la mitad la cantidad, aproximadamente.

La aplicación sucesiva de este algoritmo es equivalente a descomponer el exponente (convirtiéndolo a base binaria) en una secuencia de cuadrados y multiplicaciones: por ejemplo

x13 = x1101bin
= x(1*2^3 + 1*2^2 + 0*2^1 + 1*2^0)
= x1*2^3 * x1*2^2 * x0*2^1 * x1*2^0
= x2^3 * x2^2 * 1 * x2^0
= x8 * x4 * x1
= (x4)2 * (x2)2 * x
= (x4 * x2)2 * x
= ((x2)2 * x2)2 * x
= ((x2 * x)2)2 * x       → algoritmo necesita sólo 5 multiplicaciones en vez de 13 - 1 = 12

Algunos ejemplos más:

  • x10 = ((x2)2*x)2 porque 10 = (1,010)2 = 23+21, algoritmo necesita 4 multiplicaciones en vez de 9
  • x100 = (((((x2*x)2)2)2*x)2)2 porque 100 = (1,100,100)2 = 26+25+22, algoritmo necesita 8 multiplicaciones en vez de 99
  • x1,000 = ((((((((x2*x)2*x)2*x)2*x)2)2*x)2)2)2 porque 103 = (1,111,101,000)2, algoritmo necesita 14 multiplicaciones en vez de 999
  • x1,000,000 = ((((((((((((((((((x2*x)2*x)2*x)2)2*x)2)2)2)2)2*x)2)2)2*x)2)2)2)2)2)2 porque 106 = (11,110,100,001,001,000,000)2, algoritmo necesita 25 multiplicaciones
  • x1,000,000,000 = ((((((((((((((((((((((((((((x2*x)2*x)2)2*x)2*x)2*x)2)2)2*x)2*x)2)2*x)2)2*x)2*x)2)2)2*x)2)2*x)2)2)2)2)2)2)2)2)2 porque 109 = (111,011,100,110,101,100,101,000,000,000)2, algoritmo necesita 41 multiplicaciones
Obtenido de "Exponenciaci%C3%B3n binaria"

Wikimedia foundation. 2010.

См. также в других словарях:

  • Exponenciación binaria — La exponenciación binaria es un algoritmo utilizado para calcular de forma rápida grandes potencias de un número dado. También es conocida como algoritmo de exponenciación por cuadrados o de elevar al cuadrado y multiplicar. Implícitamente… …   Enciclopedia Universal

  • Multiplicador modular inverso — Saltar a navegación, búsqueda El multiplicador modular inverso de un entero n módulo p es un entero m tal que n 1 ≡ m (mod p) Esto significa que es el multiplicador inverso en el anillo de los enteros módulo p. Es equivalente a mn ≡ 1 (mod p) El… …   Wikipedia Español

  • Inverso multiplicativo (aritmética modular) — Este artículo o sección sobre matemáticas necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 16 de abril de 2011. También puedes …   Wikipedia Español

  • RSA — En criptografía, RSA (Rivest, Shamir y Adleman) es un sistema criptográfico de clave pública desarrollado en 1977. Es el primer y más utilizado algoritmo de este tipo y es válido tanto para cifrar como para firmar digitalmente. La seguridad de… …   Wikipedia Español

  • Fórmula de Bailey-Borwein-Plouffe — La fórmula de Bailey Borwein Plouffe (o fórmula BBP) permite calcular el enésimo dígito de π en base 2 (o 16) sin necesidad de hallar los precedentes, de una manera rápida y utilizando muy poco espacio de memoria en la computadora. Simon Plouffe… …   Wikipedia Español

  • Criptografía de curva elíptica — Saltar a navegación, búsqueda La Criptografía de Curva Elíptica (CCE) es una variante de la criptografía asimétrica o de clave pública basada en las matemáticas de las curvas elípticas. Sus autores argumentan que la CCE puede ser más rápida y… …   Wikipedia Español

  • Análisis de primalidad AKS — Saltar a navegación, búsqueda El análisis de primalidad AKS o algoritmo AKS es un algoritmo determinista que decide en tiempo polinómico si un número natural es primo o compuesto. Fue diseñado por los científicos de computación Manindra Agrawal,… …   Wikipedia Español

  • Test de Lucas — En teoría de números, el test de Lucas es un test de primalidad para un número natural n y requiere que los factores primos de n − 1 sean conocidos. Si existe un número natural a menor que n y mayor que 1 que verifica las condiciones así como… …   Wikipedia Español

  • Test de primalidad — El 39º número primo de Mersenne era el mayor conocido hasta la fecha de creación de este artículo. La cuestión de la determinación de si un número n …   Wikipedia Español

  • Test de primalidad de Miller-Rabin — El Test de primalidad de Miller Rabin es un test de primalidad, es decir, un algoritmo para determinar si un número dado es primo, similar al test de primalidad de Fermat. Su versión original fue propuesta por G. L. Miller, se trata de un… …   Wikipedia Español


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»