Exponenciación por cuadrado

En matemáticas y programación informática , la exponenciación por cuadrado es un método general para el cálculo rápido de grandes potencias enteras positivas de un número o, de manera más general, de un elemento de un semigrupo , como un polinomio o una matriz cuadrada . Algunas variantes se conocen comúnmente como algoritmos de cuadrado y multiplicación o exponenciación binaria . Estos pueden ser de uso bastante general, por ejemplo, en aritmética modular o en la potenciación de matrices. Para los semigrupos para los que se utiliza comúnmente la notación aditiva , como las curvas elípticas utilizadas en criptografía , este método también se conoce como doble y suma .

Método básico

Versión recursiva

El método se basa en la observación de que, para cualquier número entero , se tiene: $n>0$ $x^{n}={\begin{cases}x\,(x^{2})^{(n-1)/2},&{\mbox{if }}n{\mbox{ is odd}}\\(x^{2})^{n/2},&{\mbox{if }}n{\mbox{ is even}}\end{cases}}$

Si el exponente $n$ es cero, entonces la respuesta es 1. Si el exponente es negativo, entonces podemos reutilizar la fórmula anterior reescribiendo el valor utilizando un exponente positivo. Es decir, $x^{n}=\left({\frac {1}{x}}\right)^{-n}\,.$

En conjunto, estos pueden implementarse directamente como el siguiente algoritmo recursivo :

En: un entero x; un entero n Fuera: x ⁿ  exp_por_elevando_al_cuadrado(x, n) Si n < 0 entonces devuelve exp_por_cuadrado(1 / x, -n); De lo contrario, si n = 0 entonces devuelve 1; De lo contrario, si n es par, entonces devuelve exp_por_cuadrado(x * x, n / 2); De lo contrario, si n es impar, entonces devuelve x * exp_por_elevando_al_cuadrado(x * x, (n - 1) / 2); función final

En cada llamada recursiva, se eliminan los dígitos menos significativos de la representación binaria de $n$ . De ello se deduce que el número de llamadas recursivas es el número de bits de la representación binaria de $n$ . Por lo tanto, este algoritmo calcula este número de cuadrados y un número menor de multiplicaciones, que es igual al número de $1$ en la representación binaria de $n$ . Este número logarítmico de operaciones se debe comparar con el algoritmo trivial que requiere $n$ $- 1$ multiplicaciones. $\lceil \log _{2}n\rceil ,$

Este algoritmo no es recursivo en la cola , lo que implica que requiere una cantidad de memoria auxiliar que es aproximadamente proporcional a la cantidad de llamadas recursivas, o quizás mayor si la cantidad de datos por iteración aumenta.

Los algoritmos de la siguiente sección utilizan un enfoque diferente y los algoritmos resultantes necesitan la misma cantidad de operaciones, pero utilizan una memoria auxiliar que es aproximadamente la misma que la memoria requerida para almacenar el resultado.

Con memoria auxiliar constante

Las variantes descritas en esta sección se basan en la fórmula

yx^{n}={\begin{cases}(yx)\,(x^{2})^{(n-1)/2},&{\mbox{if }}n{\mbox{ is odd}}\\y\,(x^{2})^{n/2},&{\mbox{if }}n{\mbox{ is even}}.\end{cases}}

Si se aplica recursivamente esta fórmula, comenzando con $y = 1$ , se obtiene eventualmente un exponente igual a $0$ , y el resultado deseado es entonces el factor izquierdo.

Esto puede implementarse como una función recursiva de cola:

 Función exp_by_squaring ( x , n ) devuelve exp_by_squaring2 ( 1 , x , n ) Función exp_by_squaring2 ( y , x , n ) si n < 0 entonces devuelve exp_by_squaring2 ( y , 1 / x , - n ) ; de lo contrario si n = 0 entonces devuelve y ; de lo contrario si n es par entonces devuelve exp_by_squaring2 ( y , x * x , n / 2 ) ; de lo contrario si n es impar entonces devuelve exp_by_squaring2 ( x * y , x * x , ( n - 1 ) / 2 ) .

La versión iterativa del algoritmo también utiliza un espacio auxiliar acotado y está dada por

 Función exp_by_squaring_iterative ( x , n ) si n < 0 entonces x := 1 / x ; n := - n ; si n = 0 entonces devuelve 1 y := 1 ; mientras n > 1 hacer si n es impar entonces y := x * y ; n := n - 1 ; x := x * x ; n := n / 2 ; devuelve x * y

La corrección del algoritmo resulta del hecho de que es invariante durante el cálculo; lo es al principio; y lo es al final. $yx^{n}$ $1\cdot x^{n}=x^{n}$ $yx^{1}=xy$

Estos algoritmos utilizan exactamente el mismo número de operaciones que el algoritmo de la sección anterior, pero las multiplicaciones se realizan en un orden diferente.

Complejidad computacional

Un breve análisis muestra que un algoritmo de este tipo utiliza elevaciones al cuadrado y, como máximo, multiplicaciones, donde denota la función base . Más precisamente, el número de multiplicaciones es uno menos que el número de unos presentes en la expansión binaria de n . Para n mayor que aproximadamente 4, esto es computacionalmente más eficiente que multiplicar ingenuamente la base consigo misma repetidamente. $\lfloor \log _{2}n\rfloor$ $\lfloor \log _{2}n\rfloor$ $\lfloor \;\rfloor$

Cada elevación al cuadrado da como resultado aproximadamente el doble del número de dígitos del anterior y, por lo tanto, si la multiplicación de dos números de d dígitos se implementa en O( d ^k ) operaciones para algún k fijo , entonces la complejidad de calcular x ⁿ está dada por

\sum \limits _{i=0}^{O(\log n)}{\big (}2^{i}O(\log x){\big )}^{k}=O{\big (}(n\log x)^{k}{\big )}.

2amétodo -ario

Este algoritmo calcula el valor de x ⁿ después de desarrollar el exponente en base 2 ^k . Fue propuesto por primera vez por Brauer en 1939. En el algoritmo siguiente utilizamos la siguiente función f (0) = ( k , 0) y f ( m ) = ( s ,  u ), donde m = u ·2 ^s con u impar.

Algoritmo:

Aporte: Un elemento x de G , un parámetro k > 0, un entero no negativo $n = (n l -1, n l -2, ..., n 0) 2 k$ y los valores precalculados . $x^{3},x^{5},...,x^{2^{k}-1}$

Producción: El elemento x ⁿ en G

y := 1; i := l - 1 mientras i ≥ 0 hacer (s, u) := f(n _i ) para j := 1 a k - s hacer y := y ² y := y * x ^u para j := 1 a s hacer y := y ² yo := yo - 1volver y

Para una eficiencia óptima, k debe ser el entero más pequeño que satisfaga ^[1]

\lg n<{\frac {k(k+1)\cdot 2^{2k}}{2^{k+1}-k-2}}+1.

Método de ventana deslizante

Este método es una variante eficiente del método 2 ^k -ario. Por ejemplo, para calcular el exponente 398, que tiene expansión binaria (110 001 110) ₂ , tomamos una ventana de longitud 3 utilizando el algoritmo del método 2 ^k^{-ario y calculamos 1, x 3} , x ⁶ , x ¹² , x ²⁴ , x ⁴⁸ , x ⁴⁹ , x ⁹⁸ , x ⁹⁹ , x ¹⁹⁸ , x ¹⁹⁹ , x ³⁹⁸ . Pero, también podemos calcular 1, x ³ , x ⁶ , x ¹² , x ²⁴ , x ⁴⁸ , x ⁹⁶ , x ¹⁹² , x ¹⁹⁹ , x ³⁹⁸ , lo que ahorra una multiplicación y equivale a evaluar (110 001 110) ₂

Aquí está el algoritmo general:

Algoritmo:

Aporte: Un elemento x de G , un entero no negativo $n =(n l -1, n l -2, ..., n 0) 2$ , un parámetro k > 0 y los valores precalculados . $x^{3},x^{5},...,x^{2^{k}-1}$

Producción: El elemento x ⁿ ∈ G .

Algoritmo:

y := 1; i := l - 1 mientras i > -1 hacer  si n _i = 0 entonces y := y ² ' i := i - 1 de lo contrario s := máx{i - k + 1, 0} mientras n _s = 0 hacer s := s + 1 ^{[notas 1]} para h := 1 a i - s + 1 hacer y := y ² u := (n _i , n _i-1 , ..., n _s ) ₂ y := y * x ^u yo := s - 1volver y

La técnica de la escalera de Montgomery

Muchos algoritmos de exponenciación no ofrecen defensa contra ataques de canal lateral . Es decir, un atacante que observe la secuencia de elevaciones al cuadrado y multiplicaciones puede recuperar (parcialmente) el exponente involucrado en el cálculo. Esto es un problema si el exponente debe permanecer secreto, como sucede con muchos criptosistemas de clave pública . Una técnica llamada " escalera de Montgomery " ^[2] aborda este problema.

Dada la expansión binaria de un entero positivo distinto de cero n = ( n _{k −1} ... n ₀ ) ₂ con n _k−1 = 1, podemos calcular x ⁿ de la siguiente manera:

x ₁ = x; x ₂ = x ²para i = k - 2 a 0 hacer  si n _i = 0 entonces x ₂ = x ₁ * x ₂ ; x ₁ = x ₁² de lo contrario x ₁ = x ₁ * x ₂ ; x ₂ = x ₂²devolver x ₁

El algoritmo realiza una secuencia fija de operaciones ( hasta log  n ): se realiza una multiplicación y elevación al cuadrado de cada bit del exponente, independientemente del valor específico del bit. Existe un algoritmo similar para la multiplicación por duplicación.

Esta implementación específica de la escalera de Montgomery aún no está protegida contra ataques de sincronización de caché : las latencias de acceso a la memoria aún pueden ser observables para un atacante, ya que se accede a diferentes variables según el valor de los bits del exponente secreto. Las implementaciones criptográficas modernas utilizan una técnica de "dispersión" para asegurarse de que el procesador siempre pase por alto la caché más rápida. ^[3]

Exponente de base fija

Existen varios métodos que se pueden emplear para calcular x ⁿ cuando la base es fija y el exponente varía. Como se puede ver, los cálculos previos desempeñan un papel fundamental en estos algoritmos.

El método de Yao

El método de Yao es ortogonal al método $2 k$ -ario, donde el exponente se desarrolla en base $b = 2 k$ y el cálculo se realiza como en el algoritmo anterior. Sean $n$ , $n i$ , $b$ y $b i$ números enteros.

Sea el exponente $n$ escrito como

n=\sum _{i=0}^{w-1}n_{i}b_{i},

donde para todos . $0\leqslant n_{i}<h$ $i\in [0,w-1]$

Sea $x i = x b i$ .

Luego el algoritmo utiliza la igualdad

x^{n}=\prod _{i=0}^{w-1}x_{i}^{n_{i}}=\prod _{j=1}^{h-1}{\bigg [}\prod _{n_{i}=j}x_{i}{\bigg ]}^{j}.

Dado el elemento $x$ de $G$ , y el exponente $n$ escrito en la forma anterior, junto con los valores precalculados $x b 0 ... x b w -1$ , el elemento $x n$ se calcula utilizando el siguiente algoritmo:

y = 1, u = 1, j = h - 1 mientras j > 0 hacer  para i = 0 a w - 1 hacer  si n _i = j entonces u = u × x ^{b _i} y = y × u j = j - 1volver y

Si fijamos $h = 2 k$ y $b i = h i$ , entonces los valores $n i$ son simplemente los dígitos de $n$ en base $h$ . El método de Yao recoge en u primero aquellos $x i$ que aparecen a la potencia más alta ⁠ ⁠ $h-1$ ; en la siguiente ronda, aquellos con potencia ⁠ ⁠ $h-2$ se recogen también en $u , etc. La variable$ y se multiplica ⁠ ⁠ $h-1$ veces por la $u$ inicial , ⁠ ⁠ $h-2$ veces por las potencias inmediatamente superiores, y así sucesivamente. El algoritmo utiliza ⁠ ⁠ $w+h-2$ multiplicaciones, y ⁠ ⁠ $w+1$ se deben almacenar elementos para calcular $x n$ . ^[1]

Método euclidiano

El método euclidiano fue introducido por primera vez en Exponenciación eficiente usando precálculo y cadenas de adición de vectores por PD Rooij.

Este método para calcular en el grupo $G$ , donde $n$ es un entero natural, cuyo algoritmo se da a continuación, utiliza la siguiente igualdad de forma recursiva: $x^{n}$

x_{0}^{n_{0}}\cdot x_{1}^{n_{1}}=\left(x_{0}\cdot x_{1}^{q}\right)^{n_{0}}\cdot x_{1}^{n_{1}\mod n_{0}},

donde . En otras palabras, se utiliza una división euclidiana del exponente $n$ $1$ por $n$ $0$ $para obtener un cociente q$ y un resto $n$ $1$ $mod$ $n$ $0$ . $q=\left\lfloor {\frac {n_{1}}{n_{0}}}\right\rfloor$

Dado el elemento base $x$ en el grupo $G$ , y el exponente escrito como en el método de Yao, el elemento se calcula utilizando valores precalculados y luego el algoritmo siguiente. $n$ $x^{n}$ $l$ $x^{b_{0}},...,x^{b_{l_{i}}}$

Iniciar bucle  Buscar ,  $M\in [0,l-1]$  tal que .  $\forall i\in [0,l-1],n_{M}\geq n_{i}$  Buscar ,  $N\in {\big (}[0,l-1]-M{\big )}$  tal que .  $\forall i\in {\big (}[0,l-1]-M{\big )},n_{N}\geq n_{i}$  Romper bucle  si .  $n_{N}=0$  Sea ,  $q=\lfloor n_{M}/n_{N}\rfloor$  y luego sea .  $n_{N}=(n_{M}{\bmod {n}}_{N})$  Calcular recursivamente ,  $x_{M}^{q}$  y luego sea .  $x_{N}=x_{N}\cdot x_{M}^{q}$ Fin bucle ; Devolver . $x^{n}=x_{M}^{n_{M}}$

El algoritmo primero encuentra el valor más grande entre los $n i$ y luego el supremo dentro del conjunto de ${ n i \ i ≠ M }$ . Luego eleva $x M$ a la potencia $q$ , multiplica este valor por $x N$ y luego asigna $x N$ el resultado de este cálculo y $n M$ el valor $n M$ módulo $n N$ .

Otras aplicaciones

El enfoque también funciona con semigrupos que no tienen la característica cero , por ejemplo, lo que permite el cálculo rápido de grandes exponentes módulo un número. Especialmente en criptografía , es útil calcular potencias en un anillo de números enteros módulo $q$ . Por ejemplo, la evaluación de

13789722341 (módulo 2345) = 2029

Tomaría mucho tiempo y mucho espacio de almacenamiento si se usara el método ingenuo de calcular $13789722341$ y luego tomar el resto cuando se divide por 2345. Incluso usar un método más efectivo tomaría mucho tiempo: elevar al cuadrado 13789, tomar el resto cuando se divide por 2345, multiplicar el resultado por 13789, y así sucesivamente.

La aplicación del algoritmo de multiplicación por cuadrado anterior , con "*" interpretado como $x * y = xy mod 2345$ (es decir, una multiplicación seguida de una división con resto), da como resultado solo 27 multiplicaciones y divisiones de números enteros, que pueden almacenarse en una sola palabra de máquina. En general, cualquiera de estos enfoques requerirá menos de $2log 2 (722340) \leq 40$ multiplicaciones modulares.

El enfoque también se puede utilizar para calcular potencias enteras en un grupo , utilizando cualquiera de las reglas

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

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

Este enfoque también funciona en semigrupos no conmutativos y suele utilizarse para calcular potencias de matrices .

De manera más general, el enfoque funciona con exponentes enteros positivos en cada magma para el cual la operación binaria es asociativa de potencia .

Recodificación de dígitos con signo

En ciertos cálculos puede ser más eficiente permitir coeficientes negativos y, por lo tanto, utilizar la inversa de la base, siempre que la inversión en $G$ sea "rápida" o haya sido calculada previamente. Por ejemplo, al calcular $x 2 k -1$ , el método binario requiere $k -1$ multiplicaciones y $k -1$ elevaciones al cuadrado. Sin embargo, se podrían realizar $k$ elevaciones al cuadrado para obtener $x 2 k$ y luego multiplicar por $x -1$ para obtener $x 2 k -1$ .

Para este fin definimos la representación de dígitos con signo de un entero $n$ de base $b$ como

n=\sum _{i=0}^{l-1}n_{i}b^{i}{\text{ with }}|n_{i}|<b.

La representación binaria con signo corresponde a la opción particular $b = 2$ y . Se denota por . Hay varios métodos para calcular esta representación. La representación no es única. Por ejemplo, tomemos $n$ $= 478$ : dos representaciones binarias con signo distintas están dadas por y , donde se utiliza para denotar $-1$ . Dado que el método binario calcula una multiplicación para cada entrada distinta de cero en la representación en base 2 de $n$ , nos interesa encontrar la representación binaria con signo con el menor número de entradas distintas de cero, es decir, la que tiene el peso de Hamming mínimo . Un método para hacer esto es calcular la representación en forma no adyacente , o NAF para abreviar, que es una que satisface y denotada por . Por ejemplo, la representación NAF de 478 es . Esta representación siempre tiene un peso de Hamming mínimo. Un algoritmo simple para calcular la representación NAF de un entero dado con es el siguiente: $n_{i}\in \{-1,0,1\}$ $(n_{l-1}\dots n_{0})_{s}$ $(10{\bar {1}}1100{\bar {1}}10)_{s}$ $(100{\bar {1}}1000{\bar {1}}0)_{s}$ ${\bar {1}}$ $n_{i}n_{i+1}=0{\text{ for all }}i\geqslant 0$ $(n_{l-1}\dots n_{0})_{\text{NAF}}$ $(1000{\bar {1}}000{\bar {1}}0)_{\text{NAF}}$ $n=(n_{l}n_{l-1}\dots n_{0})_{2}$ $n_{l}=n_{l-1}=0$

 $c_{0}=0$ para  $i = 0$ a l  $- 1$  devuelve  $c_{i+1}=\left\lfloor {\frac {1}{2}}(c_{i}+n_{i}+n_{i+1})\right\rfloor$   $n_{i}'=c_{i}+n_{i}-2c_{i+1}$  $(n_{l-1}'\dots n_{0}')_{\text{NAF}}$

Otro algoritmo de Koyama y Tsuruoka no requiere la condición de que ; aún así minimiza el peso de Hamming. $n_{i}=n_{i+1}=0$

Alternativas y generalizaciones

La exponenciación por elevación al cuadrado puede considerarse un algoritmo de exponenciación por cadena de adición subóptimo : calcula el exponente mediante una cadena de adición que consiste en duplicar exponentes repetidos (elevaciones al cuadrado) y/o incrementar exponentes en uno (multiplicando por x ) solamente. En términos más generales, si se permite sumar los exponentes calculados previamente (multiplicando esas potencias de x ) , a veces se puede realizar la exponenciación utilizando menos multiplicaciones (pero generalmente utilizando más memoria). La potencia más pequeña donde esto ocurre es para n = 15:

x^{15}=x\times (x\times [x\times x^{2}]^{2})^{2}

(elevar al cuadrado, 6 multiplicado),

x^{15}=x^{3}\times ([x^{3}]^{2})^{2}

(cadena de adición óptima, 5 se multiplica si se reutiliza x ^{3 ).}

En general, encontrar la cadena de adición óptima para un exponente dado es un problema difícil, para el cual no se conocen algoritmos eficientes, por lo que las cadenas óptimas se utilizan típicamente solo para exponentes pequeños (por ejemplo, en compiladores donde las cadenas para potencias pequeñas han sido pretabuladas). Sin embargo, hay una serie de algoritmos heurísticos que, si bien no son óptimos, tienen menos multiplicaciones que la exponenciación por cuadrado a costa de trabajo contable adicional y uso de memoria. Independientemente, el número de multiplicaciones nunca crece más lentamente que Θ (log n ), por lo que estos algoritmos mejoran asintóticamente con respecto a la exponenciación al elevar al cuadrado solo por un factor constante en el mejor de los casos.

Véase también

Notas

^ En esta línea, el bucle encuentra la cadena más larga de longitud menor o igual a k que termina en un valor distinto de cero. No es necesario calcular todas las potencias impares de 2 hasta , y solo se deben considerar aquellas específicamente involucradas en el cálculo. $x^{2^{k}-1}$

Referencias

^ ab Cohen, H.; Frey, G., eds. (2006). Manual de criptografía de curvas elípticas e hiperelípticas . Matemáticas discretas y sus aplicaciones. Chapman & Hall/CRC. ISBN 9781584885184.
^ Montgomery, Peter L. (1987). "Aceleración de los métodos de factorización de Pollard y de curva elíptica" (PDF) . Matemáticas. Computación . 48 (177): 243–264. doi : 10.1090/S0025-5718-1987-0866113-7 .
^ Gueron, Shay (5 de abril de 2012). "Implementaciones de software eficientes de exponenciación modular" (PDF) . Journal of Cryptographic Engineering . 2 (1): 31–43. doi :10.1007/s13389-012-0031-5. S2CID 7629541.