Algoritmos para módulo de exponenciación rápida

Los algoritmos de exponenciación de módulo rápido son un tipo de algoritmos de exponenciación de módulo que se utilizan ampliamente en varios criptosistemas para acelerar las operaciones computacionales con grandes números.

Método usando el Teorema del Resto Chino

Descripción del método

Que sea necesario calcular dónde los números son lo suficientemente grandes y que el módulo se descomponga en divisores primos . Luego, para un módulo de exponenciación rápido, puede usar el teorema del resto chino y resolver el sistema de ecuaciones (habiendo calculado previamente los residuos usando el teorema de Fermat, donde ): $S=x^{a}{\bmod{n}}$ $x,a,n$ $n=p_{1}p_{2}...p_{j}$ $x^{a}\equiv r_{i}{\pmod {p_{i}}}$ $i=1,2,...,j$

${\begin{casos}x^{a}\equiv r_{1}{\pmod {p_{1}}},\qquad 0\leqslant r_{1}<p_{1}\\x^{a}\ equiv r_{2}{\pmod {p_{2}}},\qquad 0\leqslant r_{2}<p_{2}\\\qquad ......\qquad \qquad \qquad .... ..\\x^{a}\equiv r_{j}{\pmod {p_{j}}},\qquad 0\leqslant r_{j}<p_{j}\\\end{casos}}$

Reemplazando con por conveniencia, resolvemos el sistema con respecto a y obtenemos . $x^{un}$ $t$ $t$ $S$

Ejemplo

Que sea necesario calcular $S=3^{5}{\bmod {3}}0$

${\begin{casos}t=3^{5}\equiv 1{\pmod {2}}\\t=3^{5}\equiv 0{\pmod {3}}\\t=3^{5 }\equiv 3{\pmod {5}}\\\end{casos}}$

Representamos el sistema en la forma

${\begin{casos}t=3^{5}=1+2u\\t=3^{5}=0+3v\\t=3^{5}=3+5w\\\end{casos} }$

Sustituyendo t de la primera ecuación en la segunda, obtenemos , luego , o , o ; $1+2u\equiv 0{\pmod {3}}$ $2u\equiv 2{\pmod {3}}$ $u\equiv 1{\pmod {3}}$ $tu=1+3h$

sustituyendo entonces t de la primera ecuación en la tercera, teniendo en cuenta la expresión para obtenemos o , entonces ; $tu$ $1+2(1+3h)\equiv 3{\pmod {5}}$ $6h\equiv 0{\pmod {5}}$ $h=0{\pmod {5}}$

entonces por lo tanto, ; $t=3^{5}\equiv 1+2(1+3\cdot 0)\equiv 3{\pmod {5}}$ $S=3^{5}{\bmod {5}}=3$

Aplicación

Se puede obtener una ganancia significativa de este algoritmo al realizar la multiplicación. La multiplicación se realizará el doble de rápido al usar este algoritmo.

Complejidad computacional

Este método le permite reducir el número de cálculos en veces. Que sea un poco largo . Con la exponenciación habitual, tomará aproximadamente módulo de multiplicaciones. Digamos que queremos calcular . Reduciendo por y el problema se reduce a calcular . Cada grado en esta notación tiene una longitud de . Por lo tanto, cada operación de exponenciación requerirá operaciones. Total requerirá multiplicaciones módulo un número primo o en lugar del módulo de multiplicación original . $3-4$ $a$ $k$ $3k/2$ $(x^{a}{\bmod {p)),x^{a}{\bmod {q)))$ $a$ $p-1$ $q-1$ $(x^{a{\bmod {(}}p-1)}{\bmod {p)),x^{a{\bmod {(}}q-1)}{\bmod {q}})$ $k/2$ $3k/4$ $2\cdot 3k/4=3k/2$ $pags$ $q$ $norte$

El método repetido de elevar al cuadrado y multiplicar

Descripción del método

Que sea necesario calcular . Imagina el grado , donde $x^{a}{\bmod{n}}$ $a=a_{j-1}2^{j-1}+a_{j-2}2^{j-2}+...+a_{2}2^{2}+a_{1}2^ {1}+a_{0}$ $a_{j}=(0,1)$

Pongámoslo en la forma: $x^{a}{\bmod{n}}$

$x^{a}{\bmod {n}}=x^{a_{j-1}2^{j-1}+a_{j-2}2^{j-2}+...+a_{ 2}2^{2}+a_{1}2^{1}+a_{0}}{\bmod {n}}=$

$=(x^{2})^{a_{j-1}2^{j-2}+a_{j-2}2^{j-3}+...+a_{1}2^{0 }}x^{a_{0}}{\bmod{n}}=$

$=((x^{2})^{2})^{a_{j-1}2^{j-3}+a_{j-2}2^{j-4}+...+a_{ 2}2^{0}}(x^{2})^{a_{1}}x^{a_{0}}{\bmod {n}}=$

$=(...((x^{2})^{2}...)^{2})^{a_{j-1}}...(x^{8})^{a_{3 }}(x^{4})^{a_{2}}(x^{2})^{a_{1}}x^{a_{0}}{\bmod {n}}$

A continuación, se calcula el valor de la expresión y se realiza la sustitución en la expresión transformada. $x^{2}{\bmod{n}}$

Esta operación se realiza hasta que se encuentra el resultado.

Ejemplo

Que sea necesario calcular . Representemos el grado como . Representemos en la forma $249^{321}{\bmod {4}}99$ $321=256+64+1=2^{8}+2^{6}+2^{0}$ $249^{321}{\bmod {4}}99$ $249^{321}{\bmod {4}}99=249^{2^{8}+2^{6}+2^{0}}{\bmod {4}}99=$

$=(((((249^{2})^{2})^{2})^{2})^{2})^{2})^{2})^{2}(( ( ((249^{2})^{2})^{2})^{2})^{2})^{2}249{\bmod {4}}99=[249^{2}\ equivalente 125({\bmod {4}}99)]=$

$=(((((125^{2})^{2})^{2})^{2})^{2})^{2})^{2}((((125^{2 })^{2})^{2})^{2})^{2}249{\bmod {4}}99=[125^{2}\equiv 156({\bmod {4}}99) ]=$

$=((((156^{2})^{2})^{2})^{2})^{2})^{2}(((156^{2})^{2}) ^{2})^{2}249{\bmod {4}}99=[156^{2}\equiv 384({\bmod {4}}99)]=$

$=((((384^{2})^{2})^{2})^{2})^{2}((384^{2})^{2})^{2}249{\ bmod {4}}99=[384^{2}\equiv 251({\bmod {4}}99)]=$

$=(((251^{2})^{2})^{2})^{2}(251^{2})^{2}249{\bmod {4}}99=[251^{2 }\equiv 127({\bmod {4}}99)]=$

$=((127^{2})^{2})^{2}127^{2}249{\bmod {4}}99=[127^{2}\equiv 161({\bmod {4}} 99)]=$

$=(161^{2})^{2}161*249{\bmod {4}}99=[161^{2}\equiv 472({\bmod {4}}99)]=$

$=472^{2}161*249{\bmod {4}}99=[472^{2}\equiv 230({\bmod {4}}99)]=$

$=230*161*249{\bmod {4}}99=447$

Aplicación

Si - primo o es el producto de dos números primos grandes, generalmente se usa el método de elevar al cuadrado y multiplicar repetidamente. Sin embargo, si es compuesto, este método generalmente se usa junto con el teorema del resto chino. $norte$ $norte$

Complejidad computacional

La complejidad promedio de este algoritmo es igual a las operaciones de multiplicar números de dos bits más las operaciones de dividir números de bits por un número de bits. Para números de -bit y más largos, este algoritmo se realiza con bastante rapidez en una computadora. $1.5a$ $a$ $1.5a$ $2a$ $a$ $1000$

Método de exponenciación de Montgomery

Historia

Este método fue propuesto en 1985 por Peter Montgomery para acelerar la exponenciación modular.

Descripción del método

En este método, cada número se asocia a una determinada imagen y todos los cálculos se realizan con , y al final se realiza la transición de la imagen al número. $X$ $F(x)$ $F(x)$

Teorema (Montgomery).

Sean coprimos enteros positivos, y . Entonces para cualquier número entero es divisible por , y . Además, si , entonces la diferencia es , o . $N,R$ $N'=(-N^{-1}){\bmod {R}}$ $X$ $y=x+N((xN'){\bmod {R)))$ $R$ $y/R\equiv xR^{-1}({\bmod {N)))$ $0\leqslant x<RN$ $y/R-((xR^{-1}){\bmod {N)))$ ${\ estilo de visualización 0}$ $norte$

Este teorema nos permite calcular de forma óptima el valor de unos convenientemente elegidos . $(xR^{-1}){\bmod {N}}$ $R$

Definición 1. Para los números , , , tales que mcd y , llamamos al resto del número la cantidad . $R$ $norte$ $X$ $(R,N)=1$ $0\leqslant x<N$ $(R,N)$ $X$ ${\overline {x}}=(xR){\bmod {N}}$

Definición 2. El producto de Montgomery de dos números enteros se llama el número $a$ $b$ $M(a,b)=abR^{-1}{\bmod {N}}$

Teorema (reglas de Montgomery). Sean los números , coprimos y . Entonces y $R$ $norte$ $0\leqslant a,b<N$ $a{\bmod {N}}=M({\overline {a}},1)$ $M({\overline {a)],{\overline {b)))={\overline {ab}}$

Es decir, para mayor claridad, escribimos la expresión para exponenciación : $X$ $3$ $M(M(M({\overline {x}},{\overline {x}}),{\overline {x}}),1)=x^{3}{\bmod {N}}$

Algoritmo (Producto de Montgomery). Sean dados los números enteros , donde es impar, y . Este algoritmo devuelve . $0\leqslant c,d<N$ $norte$ $R=2^{s}>N$ $M(c, d)$

1.[Función M Montgomery]

M(c, d)

{

x=cd

;

z=y/z

; //De acuerdo con el teorema (Montgomery) . 2.[Resultado correcto] si ;

(z\geqslant N)z=zN

volver ;

z

}

Algoritmo (método de exponenciación de Montgomery). Deje que los números , y se elijan de la misma manera que para el algoritmo (producto de Montgomery). Este algoritmo devuelve . Denotamos bits binarios por . $0\leqslant x<N$ $y>0$ $R$ $x^{y}{\bmod {N}}$ $(y_{0},...,y_{D-1})$ $y$

1.[Configuración inicial]

{\overline {x}}=(xR){\bmod {N}}

; //Usando algún método de división con resto.

{\overline {p}}=R{\bmod {N}}

; //Usando algún método de división con resto. 2.[Esquema de exponenciación] para {

(D-1\geqslant j\geqslant 0)

{\sobrelínea {p}}=M({\sobrelínea {p}},{\sobrelínea {p}})

; //usando el algoritmo(producto de Montgomery) . si ;

(y_{i}==1){\sobrelínea {p}}=M({\sobrelínea {p}},{\sobrelínea {x}})

} // Ahora es igual a .

{\overline {p}}

{\sobrelínea {x}}^{y}

3.[Final grado]

M({\sobrelínea {p)),1)

;

Como resultado, obtenemos una imagen a partir de la cual podemos obtener el resultado final , y la expresión se calcula de antemano. Para el producto de dos números, el resultado se verá como ${\overline {x}}=xR{\bmod {N}}$ $x={\overline {x}}R^{-1}{\bmod {N}}$ $R^{-1}{\bmod {N}}$ $z={\overline {z}}R^{-1}{\bmod {N}}={\overline {x}}{\overline {y}}R^{-1}{\bmod {N}} \equiv {\frac ((\overline {x}}{\overline {y}}-({\overline {x}}{\overline {y}}(N^{-1}{\bmod {R}} ){\bmod {R)))N}{R}}{\bmod {N}}$

Ejemplo

Sea , y quiera multiplicar dos números y (es decir, el cuadrado) $N=11$ $b=R=2^{5}=32>N$ $x=3$ $x=3$ $X$

$3$ tiene una imagen $3\cdot R{\bmod {N}}=96{\bmod {1}}1=8$

(para comprobar tiene una imagen ) $9$ $9\cdot R{\bmod {N}}=288{\bmod {1}}1=2$

Multiplicamos las imágenes:

$w={\sobrelínea {x}}\cdot {\sobrelínea {x}}=64$ ,

Hacemos la transición de la imagen de multiplicación a la preimagen deseada

$q=N^{-1}{\bmod{R}}=3$ ,

$u=-w\cdot q{\bmod {R}}=-64\cdot 3{\bmod {3}}2=-192{\bmod {3}}2=0$ ,

${\overline {z}}=(w+u\cdot N)/R=(64+0\cdot 32)/32=2$

En consecuencia, el prototipo $z={\overline {z}}\cdot R^{-1}{\bmod {N}}=2\cdot 32^{-1}{\bmod {1}}1=9$

Aplicación

Este método tiene una ventaja de rendimiento sobre el método repetido de elevar al cuadrado y multiplicar, ya que la multiplicación módulo de dos números es mucho más rápida.

Complejidad computacional

Este método te permite reducir (para valores grandes de ) el cálculo de la función a una multiplicación de dos números de tamaño . La complejidad de la multiplicación de Montgomery se estima como . $norte$ ${\ estilo de visualización \ nombre del operador {mod}}$ $norte$ $O(n^{2})$

Algoritmo usando el método de la "escuela"

Descripción del método

Para mayor claridad, considere el método para la base , es decir, realizaremos cálculos en - sistema numérico binario (o binario, ya que ). La base tiene una ventaja, ya que la operación de división por se desplaza hacia la derecha y la multiplicación por se desplaza hacia la izquierda. $B=2$ $B$ $B=2$ $B=2$ $2$ $2$

Definición 1. La representación de un número entero no negativo en un sistema numérico con base (o notación -aria de un número ) es la secuencia más corta de números enteros , llamados los dígitos de la entrada, tal que cada uno de estos dígitos satisface la desigualdad , y la igualdad $X$ $B$ $B$ $X$ $(x_{yo})$ $0\leqslant x_{i}<B$ $x=\sum_{i=0}^{D-1}x_{i}B^{i}$

Por ejemplo, considere el algoritmo binario para tomar del producto . ${\ estilo de visualización \ nombre del operador {mod}}$ $xy$

Algoritmo (algoritmo binario para multiplicar y sacar el resto). Sean dados enteros positivos tales que , . Este algoritmo devuelve el resultado de una operación compuesta . Suponemos que la representación binaria del número se da según la definición 1 , por lo que los bits del número son de la forma , y es el bit más significativo. $X$ $y$ $0\leqslant x$ $y<N$ $(xy){\bmod {N}}$ $X$ $X$ $(x_{0},...,x_{D-1})$ $x_{D-1}>0$

1.[Configuración inicial]

s=0

; 2.[Convertir todos los bits]

D

para {

(D-1\geqslant j\geqslant 0)

s=2s

; si ;

(s\geqslant N)s=sN

si ;

(x_{j}==1)s=s+y

si ;

(s\geqslant N)s=sN

} volver ;

s

Este método tiene una desventaja: no aprovecha la aritmética de múltiples bits disponible en cualquier computadora moderna. Por ello, se suelen utilizar bases grandes . $B$ $2$

Complejidad computacional del método "escuela"

Una expresión de la forma tiene una estimación de complejidad computacional: $a^{b}({\bmod {n)))$ $O_{s}((\log n)^{3})$

Véase también

Notas

Literatura

Crandall Richard, Pomerance Carl. Números primos: aspectos criptográficos y computacionales / Ed. y con prefacio. V. N. Chubarikova .. - M .: URSS:: Book House "LIBROKOM", 2011. - 664 p. - ISBN 978-5-453-00016-6 , 978-5-397-03060-2.
Moldovyan NA Mínimo teórico y algoritmos de firma digital. - San Petersburgo: BVH-Petersburg: Book House "LIBROKOM", 2010. - 304 p. - ISBN 978-5-9775-0585-7 .
Ferguson, Niels, Schneier, Bruce. Criptografía práctica. - M .: Williams Publishing House, 2004. - 432 p. — ISBN 5-8459-0733-0 .
Mao V. Criptografía moderna : Teoría y práctica / trad. D. A. Klyushina - M. : Williams , 2005. - 768 p. — ISBN 978-5-8459-0847-6