Algoritmos de exponenciación rápida

Los algoritmos de exponenciación rápida ( algoritmo de exponenciación dicotómica , algoritmo de exponenciación binaria) son algoritmos diseñados para elevar un número a una potencia natural en menos multiplicaciones de las necesarias para determinar el grado [1] . Los algoritmos se basan en que para elevar un número a una potencia no es necesario multiplicar una vez el número por sí mismo , sino que se pueden multiplicar potencias ya calculadas. En particular, si es la potencia de dos, entonces para elevar a una potencia basta con elevar el número al cuadrado , gastando multiplicaciones en lugar de . Por ejemplo, para elevar un número a la octava potencia, en lugar de realizar siete multiplicaciones , puedes elevar el número al cuadrado ( ), luego elevar el resultado al cuadrado nuevamente para obtener la cuarta potencia ( ), y finalmente elevar el resultado nuevamente al cuadrado y obtener la respuesta ( ). $X$ $norte$ $X$ $norte$ $X$ $norte$ $n=2^k$ $norte$ $k$ $k$ $2^k$ $X$ $x\cdot x\cdot x\cdot x\cdot x\cdot x\cdot x\cdot x$ $x^{2}=x\cdot x$ ${\displaystyle x^{4}=x^{2}\cdot x^{2))$ ${\displaystyle x^{8}=x^{4}\cdot x^{4))$

Además, algunos algoritmos para una mayor optimización utilizan el hecho de que la operación de elevar al cuadrado es más rápida que la operación de multiplicación debido al hecho de que los dígitos en el factor se repiten al elevar al cuadrado [2] .

El algoritmo de exponenciación binaria fue propuesto por primera vez en el siglo XV por el matemático persa Al-Kashi [3] .

Estos algoritmos no siempre son óptimos. Por ejemplo, cuando se usa el esquema de izquierda a derecha, exponenciar rápidamente n = 15 requerirá tres multiplicaciones y tres elevaciones al cuadrado, aunque elevar a la potencia 15 se puede realizar en 3 multiplicaciones y 2 elevaciones al cuadrado [4] . La potenciación óptima corresponde a la construcción de la cadena aditiva más corta .

Descripción

El algoritmo principal para la exponenciación rápida es el esquema de "izquierda a derecha". Recibe su nombre del hecho de que los bits del exponente se ven de izquierda a derecha, es decir, de mayor a menor [5] .

Dejar

n=(\sobrelínea {m_{{k}}m_{{k-1}}...m_{{1}}m_{{0}}})_{2}

es una representación binaria de grado n , es decir,

n=m_{{k}}\cdot 2^{{k}}+m_{{k-1}}\cdot 2^{{k-1}}+\dots +m_{{1}}\cdot 2 +m_{{0}},

donde _ Después $m_{{k}}=1,m_{{i}}\in\{0,1\}$

x^{n}=x^{((\dots((m_{k} \cdot 2+m_{k-1}) \cdot 2+m_{k-2}) \cdot 2+\dots) \cdot 2+m_{1}) \cdot 2 + m_{0}}=((\dots(((x^{m_{k}})^{2} \cdot x^{m_{k-1}}) ^{2}\puntos)^{2} \cdot x^{m_{1}})^2 \cdot x^{m_{0}}

[5] .

La secuencia de acciones al usar este esquema se puede describir de la siguiente manera:

Representa el exponente n en forma binaria
Si = 1, entonces el resultado actual se eleva al cuadrado y luego se multiplica por x. Si = 0, entonces el resultado actual simplemente se eleva al cuadrado [6] . El índice i cambia de k -1 a 0 [7] . $mi$ $mi$

Por lo tanto, el algoritmo de exponenciación rápida se reduce a un análogo multiplicativo del esquema de Horner [6] :

{\begin{Bmatrix}s_{1}=x\\s_{{i+1}}=s_{i}^{2}\cdot x^{{m_{{ki))))\\i=1 ,2,\puntos,k\end{Bmatriz}}.

Generalizaciones

Sea el par ( S , *) un semigrupo , entonces podemos llamar a la operación * multiplicación y definir la operación de elevar a una potencia natural:

a^{n}=\left\{{\begin{matriz}{ll}a&n=1\\a*\left(a^{{n-1}}\right)&n>1\end{matriz}} \Correcto.

Entonces, para calcular los valores de un n en cualquier semigrupo (en particular, en un grupo abeliano ), se pueden usar algoritmos de exponenciación rápida [8] .

Ejemplos de resolución de problemas

Aplicando el algoritmo, calculamos 21 13 :

{\ estilo de visualización 13_{10}=1101_{2))

m_{3}=1,m_{2}=1,m_{1}=0,m_{0}=1

{\begin{alineado}21^{13}&=(((1\cdot 21^{m_{3)))^{2}\cdot 21^{m_{2)))^{2} \cdot 21^{m_{1}})^{2}\cdot 21^{m_{0}}\\&=(((1\cdot 21^{1})^{2}\cdot 21^{ 1})^{2}\cdot 21^{0})^{2}\cdot 21^{1}\\&=(((1\cdot 21)^{2}\cdot 21)^{2} \cdot 1)^{2}\cdot 21\\&=((21^{2}\cdot 21)^{2})^{2}\cdot 21\\&=((441\cdot 21)^ {2})^{2}\cdot 21\\&=85766121^{2}\cdot 21\\&=154472377739119461\end{alineado}}

Esquema de derecha a izquierda

En este esquema, a diferencia del esquema "de izquierda a derecha", los bits del exponente se visualizan de menor a mayor [5] .

La secuencia de acciones en la implementación de este algoritmo.

Exprese el exponente n en binario.
Establezca la variable auxiliar z igual al número x.
1. Si , entonces el resultado actual se multiplica por z y el número z se eleva al cuadrado. Si = 0, entonces solo necesitas elevar al cuadrado z [6] . En este caso, el índice i , a diferencia del esquema de izquierda a derecha, varía de 0 a k - 1 inclusive [7] . ${\ estilo de visualización m_ {i} = 1}$ $mi$

Este circuito contiene tantas multiplicaciones y cuadraturas como el circuito de "izquierda a derecha". Sin embargo, a pesar de esto, el esquema de izquierda a derecha es más rentable que el esquema de derecha a izquierda, especialmente si el exponente contiene muchas unidades. El punto es que en el esquema, de izquierda a derecha, la operación resultado = resultado · x contiene un multiplicador x constante . Y para x pequeña (que suele ser el caso en las pruebas de primalidad), la multiplicación será rápida. Por ejemplo, para x = 2 podemos reemplazar la operación de multiplicación con la operación de suma [7] .

La justificación matemática del funcionamiento de este algoritmo se puede representar mediante la siguiente fórmula:

d=a^{n}=

= a^{\sum_{i=0}^k m_i\cdot 2^i} =

= a^{m_0}\cdot a^{2m_1}\cdot a^{2^2*m_2}\cdot ... \cdot a^{2^k*m_k}=

= a^{m_0}\cdot (a^2)^{m_1}\cdot (a^{2^2})^{m_2}\cdot ... \cdot (a^{2^k})^{ m_k}=

=\prod _{{i=0}}^{k}{(a^{{2^{{i}}}})^{{m_{i}}}}

[9] .

ejemplo _ Calculemos el valor 21 13 usando el esquema de exponenciación de derecha a izquierda .

i	0	una	2	3
$un^{2^{i}}$	21	441	194 481	37 822 859 361
$m_1$	una	0	una	una

21 194 481 = 4084 101
4084 101 37 822 859 361 = 154 472 377 739 119 461

Complejidad computacional

Tanto para los esquemas de izquierda a derecha como de derecha a izquierda, el número de operaciones de elevación al cuadrado es el mismo y es igual a k, donde k es la longitud del exponente n en bits, . El número de operaciones de multiplicación necesarias es igual al peso de Hamming , es decir, el número de elementos distintos de cero en la representación binaria del número n . En promedio, se requieren operaciones de multiplicación [6] . $k \sim \ln{n}$ $\frac{1}{2}\cdot\ln{n}$

Por ejemplo, para elevar un número a la centésima potencia, este algoritmo requerirá solo 8 operaciones de multiplicación y elevación al cuadrado [5] .

A modo de comparación, con el método de exponenciación estándar, se requiere una operación de multiplicación, es decir, el número de operaciones se puede estimar como [10] . $n-1$ $En)$

Optimización de algoritmos

Generalmente, la operación de elevar al cuadrado es más rápida que la operación de multiplicación. El método de la ventana le permite reducir el número de operaciones de multiplicación y, por lo tanto, hacer que el algoritmo de exponenciación sea más óptimo [8] .

La ventana es en realidad la base del sistema numérico [7] . Sea w el ancho de la ventana, es decir, se tienen en cuenta w caracteres del indicador a la vez.

Considere el método de la ventana.

Para x i precalculado $yo = \overline {0, 2^w-1}$
El exponente se presenta de la siguiente forma: , donde $n = \sum_{i=0}^{k/w}{n_i\cdot2^{i\cdot w}}$ $n_i \in {(0, 1, ..., 2^w-1)}$
Sea y la variable en la que se calculará el resultado final. deja _ $y=x^{n_{k/w}}$
Para todo i = k/w - 1, k/w - 2, ..., 0, haga lo siguiente:
1. $y = y^{2^w}$
2. $y = y\cdot x^{n_i}$ [8] .

Este algoritmo requiere k elevar al cuadrado, pero el número de multiplicaciones se reduce a k/w en promedio [8] .

Aún más eficaz es el método de la ventana deslizante. Se encuentra en el hecho de que el ancho de la ventana durante la ejecución del proceso puede cambiar:

El exponente se representa como , donde , y e i+1 — e i ≥ w . $n = \sum_{i=0}^{l}{n_i\cdot2^{e_i}}$ $n_i \in {(1, 3, 5, ..., 2^w-1)}$
Para x i se calcula . Además, designaremos x i como x i . $yo = (1, 3, 5, ..., 2^w-1)$
Sea y la variable en la que se calculará el resultado final. deja _ $y=x^{n_{l}}$
Para todo i = l - 1, l - 2, ..., 0, haga lo siguiente:
1. Para todo j de 0 a e i+1 - e i - 1 y cuadrado
2. $j = m_i$
3. $y = y\cdot x_j$
Para todo j de 0 a e 0 - 1 y cuadrado [8] .

El número de operaciones de exponenciación en este algoritmo es el mismo que en el método de la ventana, pero el número de operaciones de multiplicación se ha reducido a l , es decir, a la media [8] . $\frac{k}{w+1}$

Por ejemplo, elevemos el número x a la potencia de 215 usando el método de la ventana deslizante El ancho de la ventana es w = 3.

215 = 27 + 5 24 + 7
y=1
y = y x = x
y se eleva al cuadrado 3 veces, ya que en este paso e 2 - e 1 -1 \u003d 7 - 4 - 1 \u003d 2, y la cuenta regresiva es desde cero, es decir, y \u003d y 8 \u003d x 8
y \u003d y x 5 \u003d x 13
y se eleva al cuadrado 4 veces, ya que en este paso e 1 - e 0 -1 \u003d 4 - 0 - 1 \u003d 3, es decir, y \u003d y 16 \u003d x 208
y \u003d y x 7 \u003d x 215

Aplicación

El algoritmo de exponenciación rápida se ha generalizado en los criptosistemas de clave pública . En particular, el algoritmo se utiliza en el protocolo RSA , el esquema ElGamal y otros algoritmos criptográficos [11] .

Véase también

Notas

↑ Shvets AN Exponenciación rápida . Fecha de acceso: 13 de noviembre de 2015. Archivado desde el original el 17 de noviembre de 2015. (indefinido)
↑ Pankratova, 2009 , pág. 7.
↑ Pankratova, 2009 , pág. once.
↑ Pankratova, 2009 , pág. diez.
↑ 1 2 3 4 Ryabko, Fionov, 2004 .
↑ 1 2 3 4 Manual, 2006 .
↑ 1 2 3 4 Crandall, Pomerance, 2011 .
↑ 1 2 3 4 5 6 Criptografía, 2005 .
↑ Gabidulin, Kshevetsky, Kolybelnikov, 2011 .
↑ Mahovenko, 2006 .
↑ Criptografía aplicada, 2002 .

Literatura

Schneier B. Algoritmos con claves públicas // Criptografía aplicada. - Triunfo, 2002. - ISBN 5-89392-055-4 .
Ryabko B. Ya. , Fionov A. N. Fundamentos de la criptografía moderna para especialistas en tecnología de la información - Mundo científico , 2004. - P. 15. - 173 p. — ISBN 978-5-89176-233-6
Smart N. Algoritmos de exponenciación // Criptografía . - Moscú: Technosfera, 2005. - S. 287 -292. — 528 pág. - ISBN 5-94836-043-1 .
Makhovenko E. B. Número - métodos teóricos en criptografía - M .: Helios ARV , 2006. - P. 154-155. — ISBN 978-5-85438-143-7
Cohen H., Frei G. Manual de criptografía de curva elíptica e hiperelíptica . - Chapman & Hall / CRC, 2006. - P. 145-150 . — 808 pág. — ISBN 1-58488-518-1 .
Pankratova I. A. Métodos numéricos teóricos de criptografía - Tomsk : TGU , 2009. - 120 p.
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Seguridad de la información : libro de texto - M .: MIPT , 2011. - P. 230-231. — 225 págs. — ISBN 978-5-7417-0377-9
Crandall R. , Pomerance K. Algoritmos de clave pública // Números primos : Aspectos criptográficos y computacionales - M .: URSS , 2011. - P. 514-520. — 663 pág. — ISBN 978-5-453-00016-6 , 978-5-397-02060-2