En matemáticas y programación de computadoras , exponenciar 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 multiplicar 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 semigrupos para los que se usa comúnmente la notación aditiva , como curvas elípticasutilizado en criptografía , este método también se conoce como doble y suma .
Método básico
El método se basa en la observación de que, para un entero positivo n , tenemos
Este método usa los bits del exponente para determinar qué potencias se calculan.
Este ejemplo muestra cómo calcular usando este método. El exponente, 13, es 1101 en binario. Los bits se utilizan en orden de izquierda a derecha. El exponente tiene 4 bits, por lo que hay 4 iteraciones.
Primero, inicialice el resultado a 1: .
- Paso 1) ; bit 1 = 1, así que calcule ;
- Paso 2) ; bit 2 = 1, así que calcule ;
- Paso 3) ; bit 3 = 0, así que hemos terminado con este paso (de manera equivalente, esto corresponde a );
- Paso 4) ; bit 4 = 1, así que calcule .
Si escribimos en binario como , entonces esto es equivalente a definir una secuencia Dejando y luego definiendo por , dónde será igual .
Esto se puede implementar como el siguiente algoritmo recursivo :
Función exp_by_squaring ( x , n ) si n < 0 entonces devuelve exp_by_squaring ( 1 / x , - n ) ; de lo contrario, si n = 0 , devuelve 1 ; de lo contrario, si n = 1 , devuelve x ; de lo contrario, si n es par , devuelve exp_by_squaring ( x * x , n / 2 ) ; de lo contrario, si n es impar , devuelve x * exp_by_squaring ( x * x , ( n - 1 ) / 2 ) ;
Aunque no es recursivo de cola , este algoritmo se puede reescribir en un algoritmo recursivo de cola introduciendo una función auxiliar:
Función exp_by_squaring ( x , n ) return 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 , devuelve y ; de lo contrario, si n = 1 , devuelve x * y ; de lo contrario, si n es par , devuelve exp_by_squaring2 ( y , x * x , n / 2 ) ; de lo contrario, si n es impar , devuelve exp_by_squaring2 ( x * y , x * x , ( n - 1 ) / 2 ) .
Una cola-recursivo variante también puede ser construido usando un par de acumuladores en lugar de una función auxiliar como se ve en la # F ejemplo siguiente. Se puede pensar que los acumuladores a1 y a2 almacenan los valores y donde i y j se inicializan a 1 y 0 respectivamente. En el caso par i se duplica y en el caso impar j se incrementa en i. El resultado final es dónde .
deje exp_by_squaring x n = deje rec _ exp x n ' a1 a2 = si n' = 0 entonces 1 elif n ' = 1 luego a1 * a2 elif n' % 2 = 0 luego _ exp x ( n ' / 2 ) ( a1 * a1 ) a2 más _ exp x ( n ' - 1 ) a1 ( a1 * a2 ) _ exp x n x 1
La versión iterativa del algoritmo también usa 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 , devuelve 1 y : = 1 ; mientras que n > 1 lo hace si n es par entonces x : = x * x ; n : = n / 2 ; si no y : = x * y ; x : = x * x ; n : = ( n - 1 ) / 2 ; devuelve x * y
Complejidad computacional
Un breve análisis muestra que tal algoritmo utiliza cuadraturas y como máximo multiplicaciones, donde denota la función de piso . Más precisamente, el número de multiplicaciones es uno menos que el número de unidades 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.
Cada cuadrado da como resultado aproximadamente el doble del número de dígitos del 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 n viene dada por
Método 2 k -ary
Este algoritmo calcula el valor de x n después de expandir el exponente en base 2 k . Fue propuesto por primera vez por Brauer en 1939. En el algoritmo siguiente hacemos uso de la siguiente función f (0) = ( k , 0) yf ( m ) = ( s , u ), donde m = u · 2 s con u extraño.
Algoritmo:
- Aporte
- Un elemento x de G , un parámetro k > 0, un número entero no negativo n = ( n l −1 , n l −2 , ..., n 0 ) 2 k y los valores precalculados .
- Producción
- El elemento x n en G
y: = 1; i: = l - 1 mientras que yo ≥ 0 lo hago (s, u): = f (n i ) para j: = 1 a k - s hacer y: = y 2 y: = y * x u para j: = 1 a s hacer y: = y 2 yo: = yo - 1volver y
Para una eficiencia óptima, k debe ser el número entero más pequeño que satisfaga [1] [ aclaración necesaria ]
Método de ventana corrediza
Este método es una variante eficiente del método 2 k -ary. Por ejemplo, para calcular el exponente 398, que tiene expansión binaria (110 001110) 2 , tomamos una ventana de longitud 3 usando el algoritmo del método 2 k -ary y calculamos 1, x 3 , x 6 , x 12 , x 24 , x 48 , x 49 , x 98 , x 99 , x 198 , x 199 , x 398 . Pero también podemos calcular 1, x 3 , x 6 , x 12 , x 24 , x 48 , x 96 , x 192 , x 199 , x 398 , lo que ahorra una multiplicación y equivale a evaluar (110 001 110) 2
Aquí está el algoritmo general:
Algoritmo:
- Aporte
- Un elemento x de G , un número entero no negativo n = ( n l −1 , n l −2 , ..., n 0 ) 2 , un parámetro k > 0 y los valores precalculados .
- Producción
- El elemento x n ∈ G .
Algoritmo:
y: = 1; i: = l - 1 mientras i> -1 lo hago si n i = 0 entonces y: = y 2 'i: = i - 1 más s: = max {i - k + 1, 0} mientras que n s = 0 hace s: = s + 1 [notas 1] para h: = 1 to i - s + 1 do y: = y 2 u: = (n i , n i-1 , ..., n s ) 2 y: = y * x u yo: = s - 1volver y
La técnica de la escalera de Montgomery
Muchos algoritmos de exponenciación no brindan defensa contra ataques de canal lateral . Es decir, un atacante que observe la secuencia de cuadraturas y multiplicaciones puede recuperar (parcialmente) el exponente involucrado en el cálculo. Esto es un problema si el exponente debe permanecer en secreto, como ocurre con muchos criptosistemas de clave pública . Una técnica llamada " 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 0 ) 2 con n k − 1 = 1, podemos calcular x n de la siguiente manera:
x 1 = x; x 2 = x 2 para i = k - 2 a 0 hacer Si n i = 0 entonces x 2 = x 1 * x 2 ; x 1 = x 1 2 más x 1 = x 1 * x 2 ; x 2 = x 2 2 devuelve x 1
El algoritmo realiza una secuencia fija de operaciones ( hasta log n ): se realiza una multiplicación y un cuadrado para 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 los ataques de tiempo 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 pierda la caché más rápida. [3]
Exponente de base fija
Hay varios métodos que se pueden emplear para calcular x n 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 -ary donde el exponente se expande en la base b = 2 k y el cálculo es como se realizó en el algoritmo anterior. Deje n , n i , b , y b i ser enteros.
Deje que el exponente n se escriba como
dónde para todos .
Sea x i = x b i .
Entonces el algoritmo usa la igualdad
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 usando el algoritmo siguiente:
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 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 x i que parecen tener el poder más alto; en la siguiente ronda los que tienen podertambién se recopilan en u , etc. La variable y se multiplicaveces con la inicial u ,veces con los siguientes poderes superiores, y así sucesivamente. El algoritmo utiliza multiplicaciones, y los elementos deben almacenarse para calcular x n . [1]
Método euclidiano
El método euclidiano se introdujo por primera vez en Exponenciación eficiente utilizando cadenas de precomputación y adición de vectores por PD Rooij.
Este método de computación en el grupo G , donde n es un entero natural, cuyo algoritmo se da a continuación, utiliza la siguiente igualdad de forma recursiva:
dónde . En otras palabras, una división euclidiana del exponente n 1 por n 0 se usa 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 escrito como en el método de Yao, el elemento se calcula usando valores precalculados y luego el algoritmo a continuación.
Iniciar bucle Buscar, tal que. Encontrar, tal que. Romper el bucle si. Dejar , y luego deja . Calcular recursivamente, y luego deja . Fin de bucle ;Regreso .
El algoritmo primero encuentra el valor más grande entre n i y luego el superior dentro del conjunto de { n i \ i ≠ M } . Entonces se plantea x M a la potencia q , multiplica este valor con x N , y entonces asigna x N el resultado de este cálculo y n M el valor n M modulo n N .
Otras aplicaciones
La misma idea 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 . También se puede usar para calcular potencias enteras en un grupo , usando la regla
- Potencia ( x , - n ) = (Potencia ( x , n )) −1 .
El método funciona en todos los semigrupos y se utiliza a menudo para calcular potencias de matrices .
Por ejemplo, la evaluación de
- 13,789 722,341 (mod 2345) = 2029
tomaría mucho tiempo y mucho espacio de almacenamiento si se usara el método ingenuo: calcule 13789 722341 , luego tome el resto cuando lo divida por 2345. Incluso usando un método más efectivo tomará mucho tiempo: cuadrado 13789, tome el resto cuando lo divida por 2345, multiplique el resultado por 13789, y así sucesivamente. Esto tomará menos de multiplicaciones modulares.
La aplicación del algoritmo 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 todos en una sola palabra de máquina.
Recodificació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 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 pueden 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
La representación binaria firmada 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, tome n = 478 : dos representaciones binarias con signo distintas están dadas por y , dónde 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 un mínimo de Hamming peso . Un método para hacer esto es calcular la representación en forma no adyacente , o NAF para abreviar, que es uno que satisface y denotado 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 entero dado con es el siguiente:
para i = 0 a l - 1 hacer regreso
Otro algoritmo de Koyama y Tsuruoka no requiere la condición de que ; todavía minimiza el peso de Hamming.
Alternativas y generalizaciones
La exponenciación por cuadratura se puede ver como un algoritmo subóptimo de exponenciación de cadena de adición : calcula el exponente mediante una cadena de adición que consiste en duplicaciones repetidas de exponentes (cuadraturas) y / o exponentes incrementales por uno (multiplicando por x ) solamente. De manera más general, si uno permite que se sume cualquier exponente previamente calculado (multiplicando esas potencias de x ), a veces se puede realizar la exponenciación usando menos multiplicaciones (pero típicamente usando más memoria). La potencia más pequeña donde ocurre esto es para n = 15:
- (al cuadrado, 6 multiplica),
- (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 generalmente solo se usan para exponentes pequeños (por ejemplo, en compiladores donde las cadenas para potencias pequeñas se han tabulado previamente ). Sin embargo, hay una serie de algoritmos heurísticos que, aunque no son óptimos, tienen menos multiplicaciones que exponenciación al elevar al cuadrado a costa de trabajo adicional de contabilidad y uso de memoria. Independientemente, el número de multiplicaciones nunca crece más lentamente que Θ (log n ), por lo que estos algoritmos solo mejoran asintóticamente tras la exponenciación al elevar al cuadrado por un factor constante en el mejor de los casos.
Ver también
- Exponenciación modular
- Cadena de suma vectorial
- Reducción de Montgomery
- Forma no adyacente
- Cadena de adición
Notas
- ^ En esta línea, el bucle encuentra la cadena más larga de longitud menor o igual que k que termina en un valor distinto de cero. No todas las potencias impares de 2 hasta deben calcularse, y solo se deben considerar aquellos específicamente involucrados en el cálculo.
Referencias
- ^ a b Cohen, H .; Frey, G., eds. (2006). Manual de criptografía de curvas elípticas e hiperelípticas . Matemáticas discretas y sus aplicaciones. Chapman y Hall / CRC. ISBN 9781584885184.
- ^ Montgomery, Peter L. (1987). "Aceleración de los métodos de factorización Pollard y la 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) . Revista de Ingeniería Criptográfica . 2 (1): 31–43. doi : 10.1007 / s13389-012-0031-5 .