Potenciació modular

En matemàtiques, més precisament en aritmètica modular, la potenciació modular és un tipus d'elevació a la potència (potenciació) feta en mòdul un enter. Es fa servir en particular en informàtica, especialment en l'àmbit de la criptografia.

Generalment, els problemes de potenciació modular prenen forma en una base donada b, un exponent e, un enter m. Es vol calcular c tal que:

c\equiv b^{e}{\pmod {m}}

Si b, e, i m són positius i b < m, llavors l'única solució c existeix amb $0\leq c<m$ . Per exemple, donats b = 5, e = 3, i m = 13, la solució c que funciona és 8.

Els problemes de potenciació modular similars a l'exemple precedent es consideren fàcils de resoldre, fins i tot si els nombres en joc són enormes. En canvi, calcular el logaritme discret (a partir de b, trobar les dades c, e, i m) es reconeix com a difícil. Aquest comportament de funció de direcció única fa la potenciació modular una bona candidata per a ser utilitzada en els algorismes de criptografia.

Presentació general

El càlcul ingenu de la potenciació modular és el següent: es multiplica e vegades el nombre b per ell mateix, i una vegada obtingut l'enter b^e, es calcula el seu residu mòdul m via l'algorisme de divisió euclidiana. Aquest mètode té dos defectes:

per una banda, el nombre de multiplicacions es pot reduir fàcilment, pel mètode general de potenciació ràpida: no cal fer més que log(e) multiplicacions.
d'altra banda, no s'aprofita l'estructura d'anell de l'àmbit en el qual es treballa: els enters mòdul m. Els càlculs es poden fer directament en aquest anell, sense passar prèviament pels enters. Per a posar en pràctica aquesta idea, per a cada multiplicació cal calcular un residu mòdul m. S'afegeixen així noves operacions (per a cada multiplicació, una divisió euclidiana), però s'hi surt guanyant pel fet que la mida de les dades a manipular es limita a la de m.

Les següents seccions de l'article tracten de la descripció d'aquestes diferents adaptacions, i discuteixen de la seva eficàcia en funció sobretot de la mida de les dades.

Mètode directe

El mètode més directe per a calcular una potenciació modular és calcular b^e directament, després prendre aquest nombre mòdul m. Aplicant aquest mètode per calcular c amb b = 4, e = 13, i m = 497:

c\equiv 4^{13}\ {\pmod {497}}

Es pot fer servir una calculadora per calcular 4¹³; això dona 67.108.864. Calculant el mòdul 497 d'aquesta quantitat (el residu de dividir-la entre 497), la resposta c és igual a 445.

Fixeu-vos que b té només una longitud d'una xifra i que e té només una longitud de dues xifres, però el valor b^e té una longitud de 10 xifres.

En criptografia, b té sovint almenys 256 xifres binàries (77 xifres decimals). Prenent b = 5 × 10⁷⁶ i e = 17, els dos tenen valors perfectament raonables. En aquest exemple, b té una longitud de 77 xifres i e té una longitud de 2 xifres, però el valor de b^e té una longitud de 1.304 xifres decimals. Aquest gènere de càlculs són possibles sobre els ordinadors moderns, però l'absoluta enormitat d'aquest gènere de nombres alenteix considerablement la velocitat dels càlculs. Com que b i e augmenten fins i tot cada vegada més per donar una seguretat millor, el valor b^e es fa impracticable.

El temps requerit per executar la potenciació depèn de l'entorn d'operacions i del processador. Si la potenciació s'executa com una sèrie de multiplicacions, llavors això requereix O(e) de temps per acabar-se.

Mètode que estalvia memòria

Un segon mètode per calcular la potenciació modular requereix més operacions que el primer mètode. Basant-se en l'exigència menor de memòria necessària, les operacions prenen, tanmateix, menys temps que anteriorment. En resulta que aquest algorisme pot resultar més ràpid:

sigui per intercanvis menors entre memòria cau i memòria
sigui per una utilització menor del swapping en el cas de memòria virtual

Aquest algorisme fa servir el fet que, per a dos enters donats b i c, les primeres relacions impliquen la següent:

b^{\prime }\equiv b\ {\pmod {m}}\ {\rm {i}}\ c^{\prime }\equiv c\ {\pmod {m}}

b^{\prime }c^{\prime }\equiv bc\ {\pmod {m}}

L'algorisme següent:

Fer c = 1, e' = 0.
Augmentar e' en 1.
Fer $c\equiv (b\cdot c)\ {\pmod {m}}$ .
Si e' < e, anar a 2. Sinó, c conté la solució correcta de $c\equiv b^{e}{\pmod {m}}$ .

Fixeu-vos que cada pas per l'étapa 3, l'equació $c\equiv b^{e'}\ {\pmod {m}}$ esdevé certa. Quan l'etapa 3 s'ha executat e cops, llavors, c conté la resposta buscada.

Reprenent l'exemple b = 4, e = 13, et m = 497. L'algorisme passa per l'etapa 3 tretze cops:

e' = 1. c = (1 × 4) (497) = 4 (497) = 4.
e' = 2. c = (4 × 4) (497) = 16 (497) = 16.
e' = 3. c = (16 × 4) (497) = 64 (497) = 64.
e' = 4. c = (64 × 4) (497) = 256 (497) = 256.
e' = 5. c = (256 × 4) (497) = 1024 (497) = 30.
e' = 6. c = (30 × 4) (497) = 120 (497) = 120.
e' = 7. c = (120 × 4) (497) = 480 (497) = 480.
e' = 8. c = (480 × 4) (497) = 1920 (497) = 429.
e' = 9. c = (429 × 4) (497) = 1716 (497) = 225.
e' = 10. c = (225 × 4) (497) = 900 (497) = 403.
e' = 11. c = (403 × 4) (497) = 1612 (497) = 121.
e' = 12. c = (121 × 4) (497) = 484 (497) = 484.
e' = 13. c = (484 × 4) (497) = 1936 (497) = 445.

La resposta final per a c és per tant 445, com en el primer mètode.

Com en el primer mètode, això requereix O(e) de temps per acabar el càlcul. No obstant això, com que els nombres emprats en aquests càlculs són més petits que els nombres emprats en els càlculs del primer algorisme, el factor constant en aquest mètode tendeix a ser més petit.

El mètode més eficient

Un tercer mètode que redueix dràsticament tant el nombre d'operacions com l'espai en memòria requereix millorar la potenciació modular. És una combinació del mètode precedent i d'un principi més general anomenat potenciació binària (coneguda també com a potenciació per quadrat).

En primer lloc, cal que l'exponent e s'expressi en notació binària. Així, e es pot escriure:

e=\sum _{i=0}^{n-1}a_{i}2^{i}

En aquesta notació, la longitud de e és de n bits. a_i pot prendre el valor 0 o 1 per a qualsevol i com que 0 ≤ i < n - 1. Per definició, a_{n - 1} = 1.

Llavors el valor b^e es pot escriure:

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 tant:

c\equiv \prod _{i=0}^{n-1}\left(b^{2^{i}}\right)^{a_{i}}\ {\pmod {m}}

Emprant aquesta idea per calcular l'exemple b = 4, e = 13, i m = 497 resulta que:

Fixeu-vos que e és igual a 1101 en base dos. Com que e té una longitud de quatre xifres només calen quatre multiplicacions:

El primer cop es calcula: base = 4, exp = 1101 (binari), i resultat = 1. Com que el bit de més a la dreta de exp és 1, resultat es canvia per (1 × 4) % 497, és a dir 4. exp es truca a la dreta i es converteix en 110 (binari), i base s'eleva al quadrat per passar a ser (4 × 4) % 497, és a dir 16.
Llavors la segona operació, el bit de més a la dreata exp és 0, result no es modifica pas. exp es trunca altre cop per esdevenir 11 (binri), i base s'eleva al quadrat i esdevé (16 × 16) % 497, és a dir 256.
Llavors la tercera operació, el bit de més a la dreta de exp és 1. result es canvia per (4 × 256) % 497, és a dir 30. exp es truca a la dreta i es converteix en 1, i base s'eleva al quadrat i dona (256 × 256) % 497, és a dir 429.
Llavors la quarta operació, el bit de la dreta de exp és 1. result es canvia a (30 × 429) % 497, és a dir 445. exp es trunca per esdevenir 0, i base s'eleva al quadrat per esdevenir (429 × 429) % 497, és a dir 151.

Aquí s'acaba el procés, com que exp és igual a zero el resultat és 445. Que coincideix amb el dels algorismes precedents. Per a més detalls vegeu potenciació binària.

El temps d'execució d'aquest algorisme és O(log e). Quan es treballa amb grans valors de e, és força més ràpid que els dos algorismes precedents.

Vegeu també

Reducció de Montgomery