Acurtar o cálculo da exponenciación modular

 por Andrés Ventas

Acurtar o cálculo da exponenciación modular

O cálculo do expoñente modular é un tema moi tratado debido ao seu uso en criptografía e evidentemente o seu uso nas claves de internet.

A exponenciación modular consiste en calcular unha expresión do tipo \[ b^e \equiv r \pmod{m},\] isto é, unha base $b$ elevada a un expoñente $e$ módulo $m$ onde temos que calcular o residuo $r$ que será un enteiro entre $0$ e $m-1$.

A cuestión problemática é que para criptografía úsase un expoñente moi grande.

Os métodos máis coñecidos son: método directo, o de memoria eficiente e o máis rápido sería o de expoñente binario. Aquí imos ver un novo método "de aproximación ao módulo" que nas probas realizadas resulta sempre máis curto que o do expoñente binario (non tanto como parecía a priori).

Os tres últimos métodos usan a propiedade modular de que o módulo do produto é igual ao produto dos módulos: \[ (b\cdot b_1) \mod{m} = (b \mod{m}) \cdot (b_1 \mod{m}) \] Imos mostrar os 4 métodos co exemplo da wikipedia Modular exponentiation \[ 4^{13} \equiv r \pmod{497}\]

Non esquezamos que se a base é maior que o módulo pódese aplicar primeiro o módulo á base, por exemplo: $501^{13} \equiv c \pmod{497} \text{ implica } 4^{13} \equiv c \pmod{497}$. Isto sería común para todos os métodos.

O método directo

O método directo sería obter $b^{e}$ e calcular o seu residuo, así \[ 4^{13}=67108864 \mod 497 = 445.\] Evidentemente para expoñentes grandes (veremos algún exemplo posterior) este método ten problemas coa capacidade da memoria e produce unha división longa computacionalmente para calcular o residuo.

Método de memoria eficiente

O método de memoria eficiente vai calculando o módulo paso a paso aumentando o expoñente nunha unidade, isto é, multiplicando pola base en cada paso: \begin{equation*} \begin{aligned} 4 & \mod 497 = 4 \\ 16 & \mod 497 = 16 \\ 64 & \mod 497 = 64 \\ 256 & \mod 497 = 256 \\ 1024 & \mod 497 = 30 \\ 30\cdot 4 = 120 & \mod 497 = 120 \\ & \text{e igualmente ata o último paso} \ldots \\ 484\cdot 4 = 1936 & \mod 497 = 445 \\ \end{aligned} \end{equation*}

Isto require 13 pasos que evidentemente para un expoñente máis grande dá un número de operacións non asumíbel.

Método de expoñente binario

Nos documentos consultados é o método actualmente considerado maís rápido. O método consiste en transformar o expoñente a binario e ir calculando en función dos 0 e 1 do expoñente en binario, temos dúas variábeis $x$ e $R$, en $x$ imos gardando o valor a calcular e en $R$ o resultado que se vai reseteando cada vez que temos un bit $1$. Ímolo ver co noso exemplo: \begin{equation*} \begin{aligned} &R \leftarrow 1 \, ( = b^0) \text{ e } x \leftarrow b = 4. \\ &\text{Paso 1) o bit 1 é 1, así que se estabelece } \\ &R \leftarrow R \cdot 4 \equiv 4 \pmod{497} ; \\ & \quad\quad \text{ agora } x \leftarrow x^2 \text{ }(= b^2) \equiv 4^2 \equiv 16 \pmod{497}.\\ &\text{ Paso 2) o bit 2 é 0, polo que non recalculamos ''R'';} \\ & \quad\quad \text{ así } x \leftarrow x^2 \ (= b^4) \equiv 16^2\equiv 256 \pmod{497}. \\ &\text{ Paso 3) o bit 3 é 1, así que recalculamos ''R''} \\ &R \leftarrow R \cdot x \text{ }(= b^5) \equiv 4 \cdot 256 \equiv 30 \pmod{497} ;\\ & \quad\quad \text{ agora } x \leftarrow x^2 \ (= b^8) \equiv 256^2 \equiv 429 \pmod{497}. \\ &\text{ Paso 4) o bit 4 é 1, así que recalculamos ''R''}\\ &R \leftarrow R \cdot x \text{ }(= b^{13}) \equiv 30 \cdot 429 \equiv 445 \pmod{497}; \end{aligned} \end{equation*} Algoritmo moi interesante, pasamos de 13 pasos a 4 e como a rebaixa de pasos é logarítmica con un expoñente máis grande a efectividade é enorme.

Método de aproximación modular

Consiste en procurar a potencia $e_1$ de $b$ máis próxima ao módulo $m$ (sería válido superiormente ou inferiormente), calcular o módulo con este resultado $b^{e_1} \equiv c_1 \pmod{m}$ e calculando a división enteira dos espoñentes $\frac{e}{e_{1}} \text{ con } e= e_1 \cdot d + r$ transformamos a expresión orixinal con cifras moito menores. Para o noso exemplo: \begin{equation*} \begin{aligned} & 4^5=1024 \text{ e } 13 = 2 \cdot 5 + 3 \\ & \quad\quad 1024 \equiv 30 \pmod{497}. \quad R=30, x=30^2\cdot 4^3 \\ & \quad\quad 30^2 \equiv -94 \pmod{497}. \\ & \quad\quad -94\cdot 64 = 6016 \equiv -52 \pmod{497}. \\ & R = 497 - 52 = 445. \end{aligned} \end{equation*} Este método sen usar o algoritmo dá moitas posibilidades de reorganizalo para acurtar e isto sería un tema de estudo para estabelecer esas melloras metodicamente, imos ver o anterior módulo $7$: \begin{equation*} \begin{aligned} &4^{13} = 2^{26} \equiv c \pmod{7} \\ &2^{3} \equiv -1 \pmod{7} \text{ e } 26 = 8\cdot 3 + 2 \\ &(-1)^8 \cdot 4\equiv 4 \pmod{7}. \end{aligned} \end{equation*} E mellor aínda, aplicando directamente Fermat: Se $a$ é un enteiro e $p$ é un primo que non divide $a$, daquela $a^{p-1} \equiv 1 \pmod{p}.$ (Emanuel Lazar) notes06-3.pdf Temos: \begin{equation*} \begin{aligned} &2^{6} \equiv 1 \pmod{7} \text{ e } 26 = 6\cdot 4 + 2 \\ &(1)^4 \cdot 4\equiv 4 \pmod{7}. \end{aligned} \end{equation*} Imos comparar con algúns exemplos vistos na rede: fast modular exponentiation (Khan Academy) \begin{equation*} \begin{aligned} &7^{256} \equiv c \pmod{13} \text{ daquela } 7^{12} \equiv 1 \pmod{13} \text{ e } 256 \equiv 4 \pmod{12} \\ &7^4 \pmod{13} \equiv (-3)^2 \pmod{13} = 9 \pmod{13}. \end{aligned} \end{equation*} Por último temos o teorema de Fermat-Euler: Se $a$ e $n$ son enteiros positivos coprimos daquela $a^{\phi(n)} \equiv 1 \pmod{n}.$ Teorema de Euler (Galipedia) Onde $\phi(n)$ é a función totiente de Euler. Sen usar ese teorema, pois a función totiente non é fácil de calcular salvo para números primos, e para números grandes é difícil saber se un número é primo, imos calcular o exemplo que aparece no artigo do teorema de Euler (ou Fermat-Euler) da Galipedia: \begin{equation*} \begin{aligned} &7^{222} \equiv c \pmod{10} \text{ así temos } 7^{2} = 49 \equiv -1 \pmod{10} \text{ e } 222= 2\cdot 111 +0. \\ &(-1)^{111} \pmod{10} \equiv -1 \pmod{10} \equiv 9 \pmod{10}. \end{aligned} \end{equation*}

Bibliografia

1. Modular exponentiation (Wikipedia)
2. Exponenciación amodular (Galipedia)
3. (Emanuel Lazar) notes06-3.pdf
4. fast modular exponentiation (Khan Academy)
5. Teorema de Euler (Galipedia)