Exponenciación de cadena de adición

Método de exponenciación por números enteros positivos que requiere un número mínimo de multiplicaciones

En matemáticas y ciencias de la computación , la exponenciación óptima de la cadena de adición es un método de exponenciación por una potencia entera positiva que requiere un número mínimo de multiplicaciones. Usando la forma de la cadena de adición más corta , con multiplicación en lugar de adición, se calcula el exponente deseado (en lugar del múltiplo) de la base . (Esto corresponde a la secuencia OEIS A003313 (Longitud de la cadena de adición más corta para n).) Cada exponenciación en la cadena se puede evaluar multiplicando dos de los resultados de exponenciación anteriores. De manera más general, la exponenciación de la cadena de adición también puede referirse a la exponenciación por cadenas de adición no mínimas construidas por una variedad de algoritmos (ya que una cadena de adición más corta es muy difícil de encontrar).

El algoritmo de cadena de adición más corta no requiere más multiplicaciones que la exponenciación binaria y, por lo general, menos. El primer ejemplo de un caso en el que funciona mejor es el de ¹⁵ , donde el método binario necesita seis multiplicaciones, pero la cadena de adición más corta requiere solo cinco:

${\displaystyle a^{15}=a\times (a\times [a\times a^{2}]^{2})^{2}\!}$(binario, 6 multiplicaciones)

${\displaystyle a^{15}=([a^{2}]^{2}\times a)^{3}\!}$(cadena de adición más corta, 5 multiplicaciones).

${\displaystyle a^{15}=a^{3}\times ([a^{3}]^{2})^{2}\!}$(también cadena de adición más corta, 5 multiplicaciones).

Por otra parte, la determinación de una cadena de adición más corta es difícil: actualmente no se conocen métodos óptimos eficientes para exponentes arbitrarios, y el problema relacionado de encontrar una cadena de adición más corta para un conjunto dado de exponentes ha demostrado ser NP-completo . ^[1] Incluso dada una cadena más corta, la exponenciación de la cadena de adición requiere más memoria que el método binario, porque potencialmente debe almacenar muchos exponentes anteriores de la cadena. Por lo tanto, en la práctica, la exponenciación de la cadena de adición más corta se utiliza principalmente para pequeños exponentes fijos para los que se puede calcular previamente una cadena más corta y no es demasiado grande.

También existen varios métodos para aproximar una cadena de adición más corta, que a menudo requieren menos multiplicaciones que la exponenciación binaria; la exponenciación binaria en sí misma es un algoritmo de cadena de adición subóptimo. La elección del algoritmo óptimo depende del contexto (como el costo relativo de la multiplicación y la cantidad de veces que se reutiliza un exponente dado). ^[2]

El problema de encontrar la cadena de adición más corta no se puede resolver mediante programación dinámica , porque no satisface el supuesto de subestructura óptima . Es decir, no es suficiente descomponer la potencia en potencias más pequeñas, cada una de las cuales se calcula mínimamente, ya que las cadenas de adición para las potencias más pequeñas pueden estar relacionadas (para compartir cálculos). Por ejemplo, en la cadena de adición más corta para un ¹⁵ anterior, el subproblema para un ⁶ debe calcularse como ( a ³ ) ² ya que a ³ se reutiliza (a diferencia de, digamos, a ⁶  =  a ² ( a ² ) ² , que también requiere tres multiplicaciones).

Suma-resta-exponencia en cadena

Si se permiten tanto la multiplicación como la división, se puede utilizar una cadena de suma-resta para obtener incluso menos multiplicaciones+divisiones totales (donde la resta corresponde a la división). Sin embargo, la lentitud de la división en comparación con la multiplicación hace que esta técnica sea poco atractiva en general. Por otro lado, para la exponenciación a potencias enteras negativas , dado que de todos modos se requiere una división, una cadena de suma-resta suele ser beneficiosa. Un ejemplo de ello es a ⁻³¹ , donde calcular 1/ a ³¹ mediante una cadena de suma más corta para a ³¹ requiere 7 multiplicaciones y una división, mientras que la cadena de suma-resta más corta requiere 5 multiplicaciones y una división:

${\displaystyle a^{-31}=a/((((a^{2})^{2})^{2})^{2})^{2}\!}$(cadena de suma-resta, 5 múltiplos + 1 división).

Para la exponenciación en curvas elípticas , la inversa de un punto ( x ,  y ) está disponible sin costo, ya que es simplemente ( x , − y ), y por lo tanto las cadenas de suma-resta son óptimas en este contexto incluso para exponentes enteros positivos. ^[3]

Referencias

1. Downey, Peter; Leong, Benton; Sethi, Ravi (1981). "Cálculo de secuencias con cadenas de adición". Revista SIAM de Computación . 10 (3): 638–646. doi :10.1137/0210047.
2. Gordon, Daniel M. (1998). "Un estudio de métodos de exponenciación rápida" (PDF) . J. Algorithms . 27 : 129–146. CiteSeerX 10.1.1.17.7076 . doi :10.1006/jagm.1997.0913. 
3. François Morain y Jorge Olivos, "Aceleración de los cálculos en una curva elíptica utilizando cadenas de adición-sustracción", RAIRO Informatique théoretique et application 24 , pp. 531-543 (1990).

• Donald E. Knuth , El arte de la programación informática, Volumen 2: Algoritmos seminuméricos , 3.ª edición, §4.6.3 (Addison-Wesley: San Francisco, 1998).
• Daniel J. Bernstein, "El algoritmo de Pippenger", que se incorporará al libro del autor "Criptografía de alta velocidad " (2002)