Exponenciación al cuadrado

En matemáticas y programación informática , la potenciació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 denominan comúnmente algoritmos de cuadrar y multiplicar o exponenciación binaria . Estos pueden ser de uso bastante general, por ejemplo en aritmética modular o potenciación de matrices. Para los semigrupos para los que se usa 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 es cero entonces la respuesta es 1 y si el exponente es negativo entonces podemos reutilizar la fórmula anterior reescribiendo el valor usando un exponente positivo. Eso es,

x^{-n}=\left({\frac {1}{x}}\right)^{n}\,.

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

En: un número entero x; un número entero sustantivo, masculino— Fuera: x ⁿ  exp_por_cuadrado(x,n) si n < 0 entonces devolver exp_by_squaring(1 / x, -n); de lo contrario si n = 0 entonces devolver 1; de lo contrario, si n es par, entonces devolver exp_by_squaring(x * x, n/2); de lo contrario, si n es impar, entonces return x * exp_by_squaring(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$ . Entonces este algoritmo calcula este número de cuadrados y un número menor de multiplicación, que es igual al número de $1$ 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. $\lceil \log _{2}n\rceil ,$

Este algoritmo no es recursivo de cola . Esto implica que requiere una cantidad de memoria auxiliar que es aproximadamente proporcional al número 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 usan 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$ , eventualmente se obtiene un exponente igual a $0$ , y el resultado deseado es entonces el factor izquierdo.

Esto se puede implementar 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 , devolverá exp_by_squaring2 ( y , x * x , n / 2 ) ; de lo contrario, si n es impar , devolverá 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 ; norte := - norte ; si n = 0 entonces devuelve 1 y := 1 ; mientras que n > 1 , hazlo si n es impar, entonces y := x * y ; norte := norte - 1 ; x := x * x ; norte := norte / 2 ; devolver x * y

La exactitud del algoritmo resulta del hecho de que es invariante durante el cálculo; está al principio; y está 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 dicho algoritmo utiliza elevaciones al cuadrado y, como máximo, multiplicaciones, donde denota la función suelo . 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 de la anterior, por lo que, si la multiplicación de dos números de d dígitos se implementa en operaciones O( d ^k ) para algunos k fijos , 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 )}.

método 2 k -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 siguiente algoritmo utilizamos la siguiente función f (0) = ( k , 0) y f ( m ) = ( s ,  u ), donde m = u ·2 ^s con Eres extraño.

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 - 1regresar 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 corredera

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 usando el algoritmo del método 2 ^k -ario y calculamos 1, x ³ , x ⁶ , x ¹² , x ^24. , 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 hazlo  si n _i = 0 entonces y := y ² ' i := i - 1 más s := máx{i - k + 1, 0} mientras que n _s = 0 do s := s + 1 ^{[notas 1]} para h := 1 a i - s + 1 do y := y ² u := (n _i , n _i-1 , ..., n _s ) ₂ y := y * x ^u yo := s - 1regresar y

Técnica de la escalera de Montgomery

Muchos algoritmos de exponenciación no proporcionan 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 ocurre con muchos criptosistemas de clave pública . Una técnica llamada " escalera de Montgomery " ^[2] aborda esta cuestió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:

x1 ₌ x; x ₂ = x ²para i = k - 2 a 0 hazlo  si n _i = 0 entonces x ₂ = x ₁ * x ₂ ; x ₁ = x ₁² más x ₁ = x ₁ * x ₂ ; x ₂ = x ₂²volver x ₁

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

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 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 garantizar que el procesador siempre pierda el caché más rápido. ^[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 juegan un papel clave 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 expande 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$ .

Entonces el algoritmo usa 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 el formulario 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 hazlo  para i = 0 a w - 1 hazlo  si n _i = j entonces u = u × x ^{b _i} y = y × u j = j - 1regresar y

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

método euclidiano

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

Este método para calcular en el grupo $G$ , donde $n$ es un entero natural, cuyo algoritmo se detalla 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}},

dónde . En otras palabras, se utiliza una división euclidiana del exponente $n$ $1$ por $n$ $0$ $para devolver 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 siguiente algoritmo. $n$ $x^{n}$ $l$ $x^{b_{0}},...,x^{b_{l_{i}}}$

Comience el bucle  Buscar ,  $M\in [0,l-1]$  de modo que .  $\forall i\in [0,l-1],n_{M}\geq n_{i}$  Encuentra ,  $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 el bucle  si .  $n_{N}=0$  Deja ,  $q=\lfloor n_{M}/n_{N}\rfloor$  y luego deja .  $n_{N}=(n_{M}{\bmod {n}}_{N})$  Calcule recursivamente y  $x_{M}^{q}$  luego deje .  $x_{N}=x_{N}\cdot x_{M}^{q}$ Fin del 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 $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 tienen la característica cero , permitiendo por ejemplo un cálculo rápido de exponentes grandes 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 utilizara el método ingenuo de calcular $13789722341$ y luego tomar el resto al dividirlo por 2345. Incluso utilizar un método más eficaz llevará mucho tiempo: elevar al cuadrado 13789, dividir el resto por 2345, multiplicar el resultado por 13789, etc.

La aplicación del algoritmo de exp por cuadrado anterior , con "*" interpretado como $x * y = xy mod 2345$ (es decir, una multiplicación seguida de una división con resto) conduce a solo 27 multiplicaciones y divisiones de números enteros, que pueden almacenarse todas. en una sola palabra de máquina. Generalmente, 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

El enfoque también funciona en semigrupos no conmutativos y se utiliza a menudo 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 en potencia .

Grabación de dígitos firmados

En ciertos cálculos puede ser más eficiente permitir coeficientes negativos y, por tanto, utilizar la inversa de la base, siempre que la inversión en $G$ sea "rápida" o se haya calculado 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$ .

Con este fin definimos la representación de dígitos con signo de un número entero $n$ en la 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 . Se denota por . 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 y , donde se usa para denotar $-1$ . Dado que el método binario calcula una multiplicación para cada entrada distinta de cero en la representación de base 2 de $n , estamos interesados en encontrar la representación binaria con signo con el menor número de entradas distintas de cero, es decir, la que tiene$ Hamming mínimo . peso . Un método para hacer esto es calcular la representación en forma no adyacente , o NAF para abreviar, que es aquella que satisface y se denota por . Por ejemplo, la representación NAF de 478 es . Esta representación siempre tiene un peso Hamming mínimo. Un algoritmo simple para calcular la representación NAF de un número entero dado 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$  regresa  $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 ; todavía minimiza el peso de Hamming. $n_{i}=n_{i+1}=0$

Alternativas y generalizaciones

La exponenciación al cuadrado puede verse como un algoritmo de exponenciación de cadena de suma subóptimo : calcula el exponente mediante una cadena de suma que consiste en duplicaciones repetidas de exponentes (cuadrados) y/o incrementos de exponentes solo en uno (multiplicando por x ). De manera más general, si uno permite sumar los exponentes previamente calculados (multiplicando esas potencias de x ), a veces se puede realizar la exponenciación usando menos multiplicaciones (pero generalmente usando 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}

(elevando al cuadrado, 6 multiplica),

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

(cadena de suma óptima, 5 se multiplica 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 generalmente se usan solo para exponentes pequeños (por ejemplo, en compiladores donde las cadenas para potencias pequeñas han sido tabuladas previamente). ). Sin embargo, hay una serie de algoritmos heurísticos que, si bien no son óptimos, tienen menos multiplicaciones que exponenciación al elevar al 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 tras la exponenciación al elevar al cuadrado solo por un factor constante en el mejor de los casos.

Ver 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 deben considerarse 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ática discreta y sus aplicaciones. Chapman y Hall/CRC. ISBN 9781584885184.
^ Montgomery, Peter L. (1987). "Acelerar los métodos de factorización de curva elíptica y Pollard" (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) . Revista de ingeniería criptográfica . 2 (1): 31–43. doi :10.1007/s13389-012-0031-5. S2CID 7629541.