Exponenciación binaria

La exponenciación binaria és un algoritme utilisat per a calcular de forma ràpida grans potencies sanceres d'un número $x$ dau. També és conegut com a potenciació per quadrats o elevar al quadrat i multiplicar. Implícitament utilisa l'expansió binaria de l'exponent. És d'us prou regular en aritmètica modular. Este algoritme és similar al de la duplicació en la multiplicació.

Versió recurrent

Fonaments

L'algoritme està basat en les següents tres propietats de la potència:

(1) $x^1=x$

(2) $x^{a+b}=x^a{x}^b$

(3) $x^{ab}={\left(x^a\right)}^b$

Usant $a=n-1$ i $b=1$ en l'equació (2) se seguix que $x^n=x^{n-1}x$. Prenent $a=\frac{n}{2}$ i $b=2$ en l'equació (3) s'obté que $x^n={\left(x^{\frac{n}{2}}\right)}^2$.

Algoritme

El següent algoritme recursivo calcula $x^n$ per a un natural $n$ dau:

$x^n=\{\begin{array}{cc}x& \text{si }n=1\\ x^{\frac{n}{2}}\times x^2& \text{si }n\text{ es par}\\ x\times x^{n-1}& \text{si }n\text{ es impar}\end{array}$

Comparat en el método original de multiplicar $x$ per sí mateix $n-1$ voltes, este algoritme només utilisa O(log n) multiplicacions i accelera el càlcul de $x^n$ tremendament; més o menys de la mateixa forma que l'algoritme de la multiplicació accelera una multiplicació sobre el método més llent de realisar una suma repetida.

Aplicacions

La mateixa idea permet el càlcul ràpit de potències molt grans en mòdul. Especialment en criptografia, és útil calcular potències en l'anell dels sancers mòdul q.

L'idea pot ser usada també per a computar potències d'número entero en un semigrupo, usant la regla

Potència(x, -n) = (Potència(x, n))^-1.

Este método funciona en qualsevol semigrupo, i és usat freqüentment per a calcular potències de matrius.

Per eixemple, l'evaluació de

13789⁷²²³⁴¹ (mod 2345)

prendria molt temps i espai d'almagasenament si el método ingenu és usat: calcular 13789⁷²²³⁴¹ i prendre el residu quan és dividit per 2345. Inclús usant un método més efectiu prendrà temps considerable: elevar 13789 al quadrat , prendre el residu quan es dividix per 2345, multiplicar el resultat per 13789, i aixina successivament. Este procés realisarà 722340 multplicaciones modular. Este algoritme està basat en l'observació que 13789⁷²²³⁴¹ = 13789(13789²)³⁶¹¹⁷⁰. Llavors, si es calcula 13789², el càlcul complet prendria 361170 multiplicacions modular. Esta és un guany en un factor de dos. Pero com el nou problema seguix sent similar a l'anterior, es pot aplicar l'observació novament, reduint a la mitat la cantitat, aproximadament.

L'aplicació successiva d'este algoritme és equivalent a descompondre l'exponent (convertint-ho a base binaria) en una seqüència de quadrats i multiplicacions: per eixemple

x¹³ = x^1101_bin

= x^{(1*2^3 + 1*2^2 + 0*2^1 + 1*2^0)}

= x^{1*2^3} * x^{1*2^2} * x^{0*2^1} * x^{1*2^0}

= x^{2^3} * x^{2^2} * 1 * x^{2^0}

= x⁸ * x⁴ * x¹

= (x⁴)² * (x²)² * x

= (x⁴ * x²)² * x

= ((x²)² * x²)² * x

= ((x² * x)²)² * x       → algoritme necessita només 5 multiplicacions en lloc de 13 - 1 = 12

Alguns eixemples més:

• x¹⁰ = ((x²)²*x)² perque 10 = (1,010)₂ = 2³+2¹, algoritme necessita 4 multiplicacions en lloc de

9 * x¹⁰⁰ = (((((x²*x)²)²)²*x)²)² perque 100 = (1,100,100)₂ = 2⁶+2⁵+2², algoritme necessita 8 multiplicacions en lloc de 99

• x^1,000 = ((((((((x²*x)²*x)²*x)²*x)²)²*x)²)²)² perque 10³ = (1,111,101,000)₂, algoritme necessita 14 multiplicacions en lloc de 999
• x^1,000,000 = ((((((((((((((((((x²*x)²*x)²*x)²)²*x)²)²)²)²)²*x)²)²)²*x)²)²)²)²)²)² perque 10⁶ = (11,110,100,001,001,000,000)₂, algoritme necessita 25 multiplicacions
• x^{1,000,000,000} = ((((((((((((((((((((((((((((x²*x)²*x)²)²*x)²*x)²*x)²)²)²*x)²*x)²)²*x)²)²*x)²*x)²)²)²*x)²)²*x)²)²)²)²)²)²)²)²)² perque 10⁹ = (111,011,100,110,101,100,101,000,000,000)₂, algoritme necessita 41 multiplicacions

Vore també

• Exponenciación modular