¿Por qué es más eficiente para calcular el exponentiation modular mediante el cálculo de la potencia de dos y no tres por ejemplo?

Question

Me enteré de exponentiation modular de este sitio web y en la exponenciación modular rápido calculan el modulo del número a la potencia de dos y repita este paso. ¿Por qué no calcular a la energía de tres? https://www.khanacademy.org/Computing/Computer-Science/Cryptography/modarithmetic/a/Fast-modular-exponentiation

Answer 1

Si queremos calcular el $x^N$, el monomials: $$x, x^2, x^4, x^8, \ldots, x^{2^{\lfloor \log_2 N \rfloor}}$$ son la única inicial de poderes tenemos que calcular (esto es $\lfloor \log_2 N \rfloor - 1$ multiplicaciones, porque obtenemos cada término por el cuadrado de la anterior legislatura). Luego escribimos $N$ en binario como $$N = \sum_{i=0}^{\lfloor \log_2 N\rfloor} a_i2^i,$$ $a_i \in \left\{0,1\right\}$. Si hay $k$ $1$s entre las $a_i$, $k$ cero sumandos de $N$, y se tarda $k$ multiplicaciones para obtener $x^N$ multiplicando el correspondiente monomials $x^{2^i}$. En el peor de los casos, realizamos $2 \log_2 N$ total de multiplicaciones de números grandes. En este análisis, se ignora el costo para escribir $N$ en binario, porque asumimos $N$ es pequeña en comparación con el poder de $x$ trataremos de ($N \ll x^N$).

Si tratamos de utilizar la base 3 en lugar de la base 2, ahora tenemos $\log_3 N$ monomials para calcular, pero cada uno lleva 2 multiplicaciones para obtener (2 multiplicaciones para obtener $x^3$$x$, otros 2 para obtener $x^9$$x^3$, etc.), así, en total $2 \log_3 N$ multiplicaciones para obtener el monomials. En analogía con los anteriores, ahora la expansión de la $N$ ha coeficientes en $\{0,1,2\}$, y cada una de las $2$ presenta un extra de la multiplicación en el paso final: $$x^{24} = x^{2(9) + 2(3)} = x^9x^9x^3x^3,$$ así que en el peor de los casos, de nuevo tenemos $2 \log_3 N$ multiplicaciones para obtener el resultado final.

Desde $$\frac{2 \log_3 x}{\log_2 x} = \frac{2\ln 2}{\ln 3} \approx 1.26,$$ esto es menos eficaz en el peor de los casos. Más que eso, el hecho de que los coeficientes de $N$ ternario tiene 3 casos en lugar de 2 hace que el algoritmo sea más complicada.

Este no es el final de la historia, porque hay maneras de evitar algunos de los extras multiplicaciones introducido por exponenciación modular en la base 3, mediante la combinación de términos que tienen coeficientes de 2: $$x^{24} = (x^9x^3)^2,$$ una técnica que puede ser ampliamente aplicada (véase esta cuestión en el CS StackExchange).

Así que no he contestado por qué (o si) de la base 2 en la práctica se utiliza en los algoritmos modernos, pero creo que han demostrado por qué la base 2 es óptimo para el algoritmo ingenuo, y por qué no hay una mejora inmediata en movimiento a partir de una base mayor.

Answer 2

Se podría pensar que la exponenciación por cubicación podría ser más rápido porque se triplica el exponente en un solo paso, mientras que la exponenciación elevando al cuadrado se duplica el exponente en un solo paso. Pero esta comparación no es justa, porque exponenciación por cubicación toma dos multiplicaciones por paso (compute $x^2$, luego se multiplica por $x$), mientras que la exponenciación al cuadrado sólo se necesita una.

Si, en lugar de "comparar manzanas con manzanas", dos multiplicaciones con exponenciación elevando al cuadrado se cuadruplica la exponente, mientras que dos multiplicaciones de exponenciación por cubicación sólo se triplica el exponente. Ahora bien, si usted caso omiso de cualquier "acceso directo" optimizaciones, multiplicaciones en aritmética modular tomar esencialmente constante de tiempo (dependiendo sólo del módulo), por lo que la exponenciación al cuadrado va a elevar el exponente más para un determinado coste computacional.

Para el procedimiento en general, la situación es un poco más complicado, porque en general $k$ no es una potencia de $2$ o $3$. En consecuencia, estos métodos tienen que realizar un paso recursivo: esta repetición equivale a la descomposición $x^k=\prod_{i=0}^n x^{b_i a^i}$ donde $b_i$ son dígitos en la base de $a$ expansión de $k$.

Así que no es una cuestión de cuánto tiempo cada uno de los factores en la recursividad se lleva a calcular, y también cómo muchos de ellos no son. El número de factores es normalmente más pequeño para$a=3$$a=2$, al menos si se utiliza la descomposición escribí anteriormente (lo cual requiere de un cuadrado paso en el extremo de una rama cuando $b_i=2$).

Aún así, ninguno de los problemas en el párrafo anterior son suficientes para dar exponenciación por cubicación de la ventaja, simplemente porque los factores que tienen mucho más tiempo de cálculo.

Answer 3

De hecho, puede aumentar la velocidad de exponenciación modular trabajando en una base diferente, y esto se realiza habitualmente por la limitada implementaciones en la vida real (por ejemplo, tarjetas inteligentes). Pero para que funcione, la base tiene que ser una potencia de $2$.

Supongamos que usted tiene que calcular el $x^e \bmod p$, y decide trabajar en base a $8$. A continuación se pre-calcular una tabla de $T$ contiene $1, x, x^2, x^3, x^4, x^5, x^6,$ $x^7$ (todas las $\bmod p$).

Ahora usted puede realizar la exponenciación (aproximadamente) de la siguiente manera:

y := 0  
Loop while bits remain in e:  
  y := y^8 mod p // Square y three times  
  i := the next three bits in the exponent e (from msb to lsb)  
  y := y*T[i] mod p // Incorporate the appropriate table entry
End Loop

La razón por la que tiene que ser una potencia de $2$ es que de lo contrario el paso y := y^8 sería demasiado lento.

Se necesita tiempo (y espacio de almacenamiento) para construir la tabla de $T$, por lo que debes elegir tu base cuidadosamente para optimizar el ahorro de tiempo. (Pero si la exponenciación se va a realizar muchas veces por la misma $x$, entonces sólo se necesita para la construcción de la tabla una vez, así que usted puede hacer tan grande como sea posible, sujeto a las limitaciones de su espacio.) También puede efectivamente el doble del tamaño de la tabla por sólo almacenar impar poderes de $x$; usted podría trabajar para usted mismo cómo hacerlo.

Tenga en cuenta que el número de squarings no se modifica por este método, por lo que no se puede lograr una velocidad de más de aproximadamente el 50% menos que el cuadrado es significativamente más rápido que el de la multiplicación.

Answer 4

Con el fin de recaudar x a la potencia N - de forma modular o de otra manera - por repetir la cuadratura o cubicación, uno tiene que agregar correctivas multiplicaciones hacer el último exponente de un resultado igual a N en la base 2 o 3, respectivamente. Esto significa que uno tiene que extraer de la base 2 (resp. base-3) dígitos de N. La ventaja de binario es que, debido a nuestro diseño de hardware de decisiones, ya tenemos la base de 2 dígitos de N; la extracción de ellos requiere solo TURNO de trabajo y las instrucciones. Para la base-3, habría que dividir por 3, de una forma mucho más costosa operación. [esto supone que N es una variable de entrada; si N es un pre-elegido constante por supuesto uno puede calcular previamente los pasos necesarios sin necesidad de realizar ningún divisiones]

Si estuviésemos en un mundo en el que nuestras decisiones de diseño favorecido alguna forma de ternario, tal vez esta pregunta habría sido preguntar el por qué de base-2 no es preferido sobre la base-3. :-)