Exponenciación por elevación al cuadrado

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

Método básico

Versión recursiva

El método se basa en la observación de que, para cualquier entero $n>0$ , uno tiene $x^{n}={\begin{cases}x\,(x^{2})^{(n-1)/2}&{\text{si }}n{\text{ es impar}},\\(x^{2})^{n/2}&{\text{si }}n{\text{ es par}}.\end{cases}}$

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

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

Entradas : un número real x ; un número entero n Salida : x ⁿLa función exp_by_squaring( x , n ) es : si n < 0, entonces devuelve exp_by_squaring(1 / x , − n ); de lo contrario, si n = 0 , entonces devuelve 1 ; de lo contrario, si n es par, entonces devuelve exp_by_squaring( x × x , n / 2) ; de lo contrario, si n es impar, entonces devuelve x × exp_by_squaring( x × x , ( n − 1) / 2); fin de la función.

En cada llamada recursiva, se elimina el dígito menos significativo de la representación binaria de $n$ . Por lo tanto, el número de llamadas recursivas es $\lceil \log _ {2}n\rceil,$ 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 1s en la representación binaria de $n$ . Este número logarítmico de operaciones debe compararse con el algoritmo trivial que requiere $n - 1$ multiplicaciones.

Este algoritmo no es recursivo de cola . Esto implica que requiere una cantidad de memoria auxiliar aproximadamente proporcional al número de llamadas recursivas, o incluso mayor si la cantidad de datos por iteración va en aumento.

Los algoritmos de la siguiente sección utilizan un enfoque diferente, y los algoritmos resultantes necesitan el mismo número de operaciones, pero utilizan una memoria auxiliar que es aproximadamente la misma que la memoria necesaria 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}&{\text{si }}n{\text{ es impar}},\\y\,(x^{2})^{n/2}&{\text{si }}n{\text{ es par}}.\end{cases}}$

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

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 viene dada por

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

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

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 dicho algoritmo utiliza $\lfloor \log _{2}n\rfloor$ cuadrados y como máximo $\lfloor \log _{2}n\rfloor$ multiplicaciones, donde $\lfloor \;\rfloor$ denota la función piso . 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 por sí misma repetidamente.

Cada elevación al cuadrado resulta en aproximadamente el doble del número de dígitos de la 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 ⁿ viene dada por

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

método 2k ^{- ario}

Este algoritmo calcula el valor de x ⁿ después de expandir el exponente en base 2 ^k . Fue propuesto por primera vez por Brauer en 1939. En el algoritmo que se muestra a continuación, utilizamos las siguientes funciones 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 ^upara j := 1 a s hacer y := y ² i := i - 1 regresar 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 ^2k -ario. Por ejemplo, para calcular el exponente 398, cuya expansión binaria es (110 001 110) ₂ , tomamos una ventana de longitud 3 usando el algoritmo del método 2k ^- ario y calculamos 1, x ³ , 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) ₂

Este es 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 demás s := max{i - k + 1, 0} mientras n _s = 0 hacer s := s + 1 ^{[ notas 1 ]} para h := 1 hasta i - s + 1 hacer y := y ² u := (n _i , n _i-1 , ..., n _s ) ₂ y := y * x ^u i := s - 1 regresar y

La técnica de escalera de Montgomery

Muchos algoritmos de exponenciación no ofrecen protección 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 representa un problema si el exponente debe permanecer secreto, como ocurre con muchos criptosistemas de clave pública . Una técnica denominada " escalera de Montgomery " ^{[ 2 ]} aborda esta preocupación.

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 hasta 0 hacer si n _i = 0 entonces x ₂ = x ₁ * x ₂ ; x ₁ = x ₁²sino x ₁ = x ₁ * x ₂ ; x ₂ = x ₂²devolver x ₁

El algoritmo realiza una secuencia fija de operaciones ( hasta log n ): se lleva a cabo una multiplicación y una elevación al cuadrado para cada bit del exponente, independientemente del valor específico de dicho 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 temporización de caché : las latencias de acceso a la memoria aún podrían ser observables para un atacante, ya que se accede a diferentes variables dependiendo del valor de los bits del exponente secreto. Las implementaciones criptográficas modernas utilizan una técnica de "dispersión" para asegurar que el procesador siempre omita la caché más rápida. ^{[ 3 ]}

Exponente de base fija

Existen varios métodos para calcular x ⁿ cuando la base es fija y el exponente varía. Como se puede observar, 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 $2k - ario$ donde el exponente se expande en base $b = 2k y$ el cálculo se realiza como en el algoritmo anterior. Sean n $,$ ni $, b$ $y$ bi $enteros$ .

Sea el exponente $n$ escrito como

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

dónde $0\leqslant n_{i}<h$ a pesar de $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 - 1 regresar y

Si establecemos $h = 2k$ 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 recopila primero en u aquellos $x i$ que aparecen en la potencia más alta . $h-1$ ; en la siguiente ronda, aquellos con poder $h-2$ También se recogen en $u,$ etc. La variable y se multiplica $h-1$ veces con $la u$ inicial, $h-2$ veces con las siguientes potencias más altas, y así sucesivamente. El algoritmo utiliza $w+h-2$ multiplicaciones , y $w+1$ Los elementos deben almacenarse para calcular $x n$ .^{[ 1 ]}

método euclidiano

El método euclidiano fue introducido por primera vez en Efficient exponentiation using precomputation and vector addition chains por PD Rooij.

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

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}},

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

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

Iniciar bucle Buscar $M\in [0,l-1]$ , de tal manera que $\forall i\in [0,l-1],n_{M}\geq n_{i}$ . Encontrar $N\in {\big (}[0,l-1]-M{\big )}$ , de tal manera que $\forall i\in {\big (}[0,l-1]-M{\big )},n_{N}\geq n_{i}$ . Salir del bucle si $n_{N}=0$ . Dejar $q=\lfloor n_{M}/n_{N}\rfloor$ y luego dejar $n_{N}=(n_{M}{\bmod {n}}_{N})$ Calcular recursivamente $x_{M}^{q}$ y luego dejar $x_{N}=x_{N}\cdot x_{M}^{q}$ . Fin del bucle ; Regresar $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 a $x N$ el resultado de este cálculo y $a n M$ el valor $n M$ módulo $n N$ .

Otras aplicaciones

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

13789722341 (módulo 2345) = 2029

$El método ingenuo de calcular 13789 \times 722341$ y luego obtener el resto de la división por 2345 llevaría muchísimo tiempo y mucho espacio de almacenamiento . Incluso un método más eficaz también llevaría mucho tiempo: elevar al cuadrado 13789, obtener el resto de la división por 2345, multiplicar el resultado por 13789, y así sucesivamente.

Aplicando el algoritmo exponencial por cuadrado mencionado anteriormente , donde "*" se interpreta como $x * y = xy mod 2345 (es decir, una multiplicación seguida de una división con resto)$ $,$ se obtienen solo 27 multiplicaciones y divisiones de enteros, las cuales pueden almacenarse en una sola palabra de máquina. En general, cualquiera de estos métodos requerirá menos de $2log₂ (722340) \leq 40$ multiplicaciones modulares.

Este 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 método también funciona en semigrupos no conmutativos y se utiliza a menudo para calcular potencias de matrices .

En términos más generales, 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, usar el inverso de la base, siempre que la inversión en $G$ $sea$ "rápida" o se haya precalculado. Por ejemplo, al calcular $x²k⁻¹$ , el método binario requiere $k⁻¹ multiplicaciones$ y $k⁻¹ elevaciones$ $al$ $cuadrado .$ $Sin$ $embargo$ , se podrían realizar $k$ elevaciones $al$ $cuadrado$ para obtener $x²k$ y luego multiplicar $por$ $x⁻¹$ $para$ obtener $x²k⁻¹ .$

Para ello definimos la representación de dígitos con signo de un entero $n$ en 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 elección particular $b = 2$ y $n_{i}\in \{-1,0,1\}$ Se denota por $(n_{l-1}\dots n_{0})_{s}$ Existen 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 vienen dadas por $(10{\bar {1}}1100{\bar {1}}10)_{s}$ y $(100{\bar {1}}1000{\bar {1}}0)_{s}$ , dónde ${\bar {1}}$ se utiliza para denotar $-1$ . Dado que el método binario calcula una multiplicación para cada entrada no nula 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 no nulas, 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 $n_{i}n_{i+1}=0{\text{ for all }}i\geqslant 0$ y denotado por $(n_{l-1}\dots n_{0})_{\text{NAF}}$ . Por ejemplo, la representación NAF de 478 es $(1000{\bar {1}}000{\bar {1}}0)_{\text{NAF}}$ Esta representación siempre tiene un peso de Hamming mínimo. Un algoritmo simple para calcular la representación NAF de un número entero dado $n=(n_{l}n_{l-1}\dots n_{0})_{2}$ con $n_{l}=n_{l-1}=0$ es lo siguiente:

 $c_{0}=0$  para  $i = 0$  a  $l - 1$  hacer  $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}$ devolver $(n_{l-1}'\dots n_{0}')_{\text{NAF}}$

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

Alternativas y generalizaciones

La exponenciación por elevación al cuadrado puede considerarse un algoritmo de exponenciación en cadena de suma subóptimo : calcula el exponente mediante una cadena de suma que consiste en duplicaciones repetidas del exponente (elevaciones al cuadrado) y/o incrementos de exponentes en uno (multiplicación por x ). 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 con menos multiplicaciones (aunque normalmente con más memoria). La potencia más pequeña en la que esto ocurre es para n = 15.

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

(elevar al cuadrado, multiplicar por 6),

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

(cadena de suma óptima, 5 multiplicaciones si se reutiliza x ^{3 ).}

En general, encontrar la cadena de suma ó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 suelen usar solo para exponentes pequeños (por ejemplo, en compiladores donde las cadenas para potencias pequeñas ya están tabuladas). Sin embargo, existen varios algoritmos heurísticos que, si bien no son óptimos, requieren menos multiplicaciones que la exponenciación por elevación al cuadrado, a costa de un mayor trabajo de gestión y uso de memoria. En cualquier caso, el número de multiplicaciones nunca crece más lentamente que Θ (log n ), por lo que estos algoritmos mejoran asintóticamente la exponenciación por elevación 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 todas las potencias impares de 2 hasta $x^{2^{k}-1}$ Es necesario realizar el cálculo, y solo se deben considerar aquellos específicamente involucrados en el cálculo.

Referencias

1 2 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). "Acelerando los métodos de factorización de Pollard y de curvas elípticas" (PDF) . Math. Comput . 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 .

[2] 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 todas las potencias impares de 2 hasta $x^{2^{k}-1}$ Es necesario realizar el cálculo, y solo se deben considerar aquellos específicamente involucrados en el cálculo.

[frey-1] 1 2 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.

[ladder-3] Montgomery, Peter L. (1987). "Acelerando los métodos de factorización de Pollard y de curvas elípticas" (PDF) . Math. Comput . 48 (177): 243– 264. doi : 10.1090/S0025-5718-1987-0866113-7 .

[4] 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 .

[ 1 ].

[ notas 1 ]

[ 2 ]

[ 3 ]

Método básico

Versión recursiva

Con memoria auxiliar constante

Complejidad computacional

método 2k - ario

Método de ventana deslizante

La técnica de escalera de Montgomery

Exponente de base fija

El método de Yao

método euclidiano

Otras aplicaciones

Recodificación de dígitos con signo

Alternativas y generalizaciones

Véase también

Notas

Referencias

método 2k ^{- ario}