Exponenciación modular

La exponenciación modular és un tipo d'exponenciación realisada sobre un mòdul. És particularment útil en ciències de la computació, especialment en el camp de la criptografia.

Una «exponenciación modular» calcula el residu quan un número entero positiu b (la base) s'eleva a la i-ésima potència (l'exponent), bⁱ, i és dividit pel sancer positiu m, cridat mòdul. En notació matemàtica, donada la base b, l'exponent i, i el mòdul m, la exponenciación modular c s'escriu: $c\equiv b^e(\mathrm{mod}m)$

Per eixemple, donat b = 5, i = 3, i m = 13, la solució, c = 8, és el restant de dividir $5^3$ per 13.

Si b, i, i m no són negatius, i b < m, llavors una única solució c existix en la propietat 0 ≤ c < m.

La exponenciación modular es pot realisar en exponent negatiu i trobant l'invers multiplicativo modular d de b mòdul m usant l'algoritme estés de Euclides. Açò és:

$c\equiv b^e\equiv d^{\left|e\right|}(\mathrm{mod}m)$ a on $e<0$ i $b\cdot d\equiv 1(\mathrm{mod}m)$

Problemes de exponenciación modular similars al descrit dalt són considerats fàcils de resoldre, inclús quan els números que es manegen són enormes.
Per un atre costat, el càlcul del logaritmo discret — és dir, la tasca de trobar l'exponent i si és donat un b, c, i m — és un problema dels considerats difícils. Este comportament de funció unidireccional fa a la exponenciación modular un candidat per al seu us en algoritmes criptográficos.

Método directe

És convenient trobar un método més aplanat per a calcular la exponenciación modular donat el pes de còmput del directe.
Per eixemple, per a obtindre c, donats b = 4, i = 13 i m = 497, per a abordar l'operació de :$c\equiv 4^{13}(\mathrm{mod}497).$, es pot calcular en primer lloc de bⁱ' i després el seu mòdul m.
Es pot apelar a la calculadora per a obtindre 67 108 864 com a resultat de 4¹³:
i després el mòdul 497 d'este valor per a determinar que c és 445.

En este cas, en un valor d'a penes un dígit per a b i solament dos para i, són 8 els de bⁱ - és dir, per a 4¹³-.
En aplicacions habituals de la criptografia, b pot presentar a lo manco 256 dígits binarios (i 77 decimals). Considerem b = Plantilla:Unité i i = 17,, valors tots perfectament raonables. En este cas, en b de 77 dígits i i de 17, són 1304 els de bⁱ.
Donada la capacitat de còmput actual este recorregut és viable pero ralentisa tant la operatoria que lo convenient és apelar una modalitat que oferixca millors condicions de seguritat per a aplegar al valor de bⁱ encara que aumenten els b i i (el càlcul de la exponenciación com a série de multiplicacions requerix un temps concorde a O(i)).

Método en menor requeriment de memòria

Un método alternatiu per a calcular la exponenciación modular en menor requeriment de memòria, resulta d'apelar a un algoritme més ràpit:

Tal algoritme apela a que, daus dos sancers b i c, les relacions preliminars impliquen que:

$b^{\prime }\equiv b(\mathrm{mod}m)\mathrm{y}{c}^{\prime }\equiv c(\mathrm{mod}m)$

$b^{\prime }c(\mathrm{mod}m)\equiv bc(\mathrm{mod}m)$

$b{c}^{\prime }(\mathrm{mod}m)\equiv bc(\mathrm{mod}m)$

L'algoritme és el següent:

1. Sent $c^{\prime }$ = 1, $e^{\prime }$ = 0.
2. Incrementar i' en 1.
3. Calcular $c^{\prime }\equiv (b\cdot c^{\prime })(\mathrm{mod}m)$.
4. Si i' < i, passar al pas 2. Si no, $c^{\prime }$ conté la solució correcta de $c\equiv b^e(\mathrm{mod}m)$.

cal senyalar que en cada cicle pel pas 3, l'equació $c\equiv b^{e^{\prime }}(\mathrm{mod}m)$ resulta verdadera. Quan s'eixecuta i voltes el pas 3, c devé la resposta buscada.

Repassem l'eixemple b = 4, i = 13, i m = 497. L'algoritme cicla 13 voltes pel pas 3:

• i' = 1. c = (4 x 1) (mod 497) = 4 (mod 497) = 4.
• i' = 2. c = (4 x 4) (mod 497) = 16 (mod 497) = 16.
• i' = 3. c = (4 x 16) (mod 497) = 64 (mod 497) = 64.
• i' = 4. c = (4 x 64) (mod 497) = 256 (mod 497) = 256.
• i' = 5. c = (4 x 256) (mod 497) = 1024 (mod 497) = 30.
• i' = 6. c = (4 x 30) (mod 497) = 120 (mod 497) = 120.
• i' = 7. c = (4 x 120) (mod 497) = 480 (mod 497) = 480.

• i' = 8. c = (4 x 480) (mod 497) = 1920 (mod 497) = 429.
• i' = 9. c = (4 x 429) (mod 497) = 1716 (mod 497) = 225.
• i' = 10. c = (4 x 225) (mod 497) = 900 (mod 497) = 403.
• i' = 11. c = (4 x 403) (mod 497) = 1612 (mod 497) = 121.
• i' = 12. c = (4 x 121) (mod 497) = 484 (mod 497) = 484.
• i' = 13. c = (4 x 484) (mod 497) = 1936 (mod 497) = 445.

La resposta final per a c és, en conseqüència, 445, com en el primer método.

Com el primer método, este requerix un temps de càlcul segons O(i). No obstant, com l'els números en joc en este càlcul són menors que aquells en els que s'opera en el primer algoritme, també ho és el factor constant involucrat.

El método més eficaç

Un tercer método, combinació del precedent en un principi més general denominat exponenciación binaria (o exponenciación ràpida o per quadrats).

Davant tot, es deu convertir l'exponent i a notació binaria, és dir, anotat com:

$e=\sum _{i=0}^{n-1}{a}_i{2}^i.$

En esta notació, la llongitut de i és de n bits. a_i pot prendre el valor 0 o 1 per a tot i tal que 0 ≤ i < n - 1. Per definició, a_{n - 1} = 1.

El valor bⁱ pot escriure's, llavors com:

$b^e=b^{\left(\sum _{i=0}^{n-1}{a}_i{2}^i\right)}=\prod _{i=0}^{n-1}{\left(b^{2^i}\right)}^{a_i}.$

La solució c és, per això:

$c\equiv \prod _{i=0}^{n-1}{\left(b^{2^i}\right)}^{a_i}(\mathrm{mod}m).$

Tal algoritme es pot implementar fàcilment en un llenguage de programació adequat. El següent eixemple s'elabora en C#. La classe Bignum representa a qualsevol número positiu gran. Les variables d'entrada són base per a la base (b), exp per a l'exponent (i) i m per al mòdul.

Bignum modpow(Bignum base, Bignum exp, Bignum m) {

   Bignum result = 1;

   while (exp > 0) {
      if ((exp & 1) > 0) result = (result * base) % m;
      exp >>= 1;
      base = (base * base) % m;
   }

   return result;

 }

Este còdic, adaptació del que apareix en la pàgina 244 de Applied Cryptography de Bruce Schneier, ISBN 0471117099, apela a un bucle simple while per a eixecutar tot el treball de càlcul necessari per a la exponenciación modular.

En la primera entrada al bucle, la variable base equival a b. No obstant, la repetida elevació al quadrat 13 voltes repetida assegura que la variable base resulte $b^{2^i}(\mathrm{mod}m)$, a on i és el número de iteraciones del bucle.

La primera llínea de còdic efectua simplement la multiplicació $\prod _{i=0}^{n-1}{\left(b^{2^i}\right)}^{a_i}(\mathrm{mod}m)$. Si a_i val zero, el còdic no s'eixecuta, lo que equival a multiplicar el total per un. Si, en canvi, a_i val un, el resultat és simplement multiplicar per la variable base (que conté el valor $b^{2^i}(\mathrm{mod}m)$ de la base original).

Per a finalisar, controlem l'eixemple corresponent a b = 4, i = 13 i m = 497. En binario, i és 1101 i com la seua llongitut és de 4 bits, el bucle s'eixecuta quatre voltes:

• En la primera entrada al bucle, els valors de les variables són: base = 4, exp = 1101 (binaire) i result = 1. Com el bit més a la dreta de exp és 1, result és reemplaçat per (1 × 4) % 497, és dir 4. exp devé 110 (binario) i base elevat al quadrat pel valor (4 × 4) % 497, és dir, 16.
• En la segona eixecució del bucle, el bit més a la dreta de exp és 0, result no es modifica. exp es trunca a la dreta i devé 11 (binario) i base s'eleva al quadrat i pansa a valdre (16 × 16) % 497, és dir, 256.
• En la tercera eixecució del bucle, el bit més a la dreta de exp és 1, result és remplazado per (4 × 256) % 497, és dir, 30. exp es trunca a la dreta i devé 1 i base és elevat al quadrat i pansa a valdre (256 × 256) % 497, és dir 429.
• En la quarta eixecució del bucle, el bit més a la dreta de exp és 1, result és remplazado per (30 × 429) % 497, és dir, 445. exp es trunca a la dreta i devé 0 i base és elevat al quadrat i pansa a valdre (429 × 429) % 497, és dir 151. (Esta última multiplicació base * base és irrellevant perque el resultat buscat, ací 445, ya és conegut.)

El bucle termina, llavors, quan exp és igual a zero i el resultat445, lo que concorda en els dos algoritmes precedents.

Els temps d'eixecució d'este algoritme resulten concorde a O(log i). Inclús quan opera en grans valors de i, és ràpit en comparació a cada u dels anteriors.

Referències

Schneier, Bruce (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition, 2nd edició, Wiley. ISBN 978-0-471-11709-4.