Exponenciação por quadrado - Exponentiation by squaring

Em matemática e programação de computadores , a exponenciação por quadrado é um método geral para cálculo rápido de grandes potências inteiras positivas de um número , ou mais geralmente de um elemento de um semigrupo , como um polinômio ou uma matriz quadrada . Algumas variantes são comumente chamadas de algoritmos de multiplicação de quadrados ou exponenciação binária . Estes podem ser de uso bastante geral, por exemplo, em aritmética modular ou alimentação de matrizes. Para semigrupos para os quais a notação aditiva é comumente usada, como curvas elípticasusado em criptografia , esse método também é conhecido como double-and-add .

Método básico

O método é baseado na observação de que, para um número inteiro positivo n , temos

${\ displaystyle x ^ {n} = {\ begin {cases} x \, (x ^ {2}) ^ {\ frac {n-1} {2}}, & {\ mbox {if}} n {\ mbox {é ímpar}} \\ (x ^ {2}) ^ {\ frac {n} {2}}, & {\ mbox {if}} n {\ mbox {é par}}. \ end {casos} }}$

Exemplo: . 13 é ímpar, portanto, pelo acima, = . ${\ displaystyle x ^ {13}}$${\ displaystyle x ^ {13}}$${\ displaystyle x ((x ^ {2}) ^ {6})}$

Pode-se escrever como um produto de expoentes na forma 2 ^k para o qual 2 ^k <13. = algum produto de , , , . Como a representação binária de 13 é 1101, ${\ displaystyle x ^ {13}}$${\ displaystyle x ^ {13}}$${\ displaystyle x ^ {8}}$${\ displaystyle x ^ {4}}$${\ displaystyle x ^ {2}}$${\ displaystyle x ^ {1}}$

${\ displaystyle x ^ {13}}$ = ${\ displaystyle (x ^ {8}) ^ {1} \ cdot (x ^ {4}) ^ {1} \ cdot (x ^ {2}) ^ {0} \ cdot (x ^ {1}) ^ {1}}$

Assim, podemos usar os bits do expoente para determinar quais potências são calculadas.

Este exemplo mostra como calcular usando este método. O expoente, 13, é 1101 em binário. Os bits são usados ​​da esquerda para a direita. O expoente possui 4 bits, portanto, existem 4 iterações. ${\ displaystyle x ^ {13}}$

Primeiro, inicialize o resultado a 1: . ${\ displaystyle r \ leftarrow 1 \, (= x ^ {0})}$

Etapa 1) ; bit 1 = 1, então calcule ;${\ displaystyle r \ leftarrow r ^ {2} \, (= x ^ {0})}$${\ displaystyle r \ leftarrow r \ cdot x \, (= x ^ {1})}$

Etapa 2) ; bit 2 = 1, então calcule ;${\ displaystyle r \ leftarrow r ^ {2} \, (= x ^ {2})}$${\ displaystyle r \ leftarrow r \ cdot x \, (= x ^ {3})}$

Etapa 3) ; bit 3 = 0, então terminamos com esta etapa (equivalentemente, isso corresponde a );${\ displaystyle r \ leftarrow r ^ {2} \, (= x ^ {6})}$${\ displaystyle r \ leftarrow r \ cdot x ^ {0} \, (= x ^ {6})}$

Etapa 4) ; bit 4 = 1, então calcule .${\ displaystyle r \ leftarrow r ^ {2} \, (= x ^ {12})}$${\ displaystyle r \ leftarrow r \ cdot x \, (= x ^ {13})}$

Se escrevermos em binário como , isso é equivalente a definir uma sequência permitindo e, em seguida, definindo para , onde será igual . ${\ displaystyle n}$${\ displaystyle b_ {k} \ cdots b_ {0}}$${\ displaystyle r_ {k + 1}, \ ldots, r_ {0}}$${\ displaystyle r_ {k + 1} = 1}$${\ displaystyle r_ {i} = r_ {i + 1} ^ {2} x ^ {b_ {i}}}$${\ displaystyle i = k, \ ldots, 0}$${\ displaystyle r_ {0}}$${\ displaystyle x ^ {n}}$

Isso pode ser implementado como o seguinte algoritmo recursivo :

  Function exp_by_squaring(x, n)
    if n < 0  then return exp_by_squaring(1 / x, -n);
    else if n = 0  then return  1;
    else if n = 1  then return  x ;
    else if n is even  then return exp_by_squaring(x * x,  n / 2);
    else if n is odd  then return x * exp_by_squaring(x * x, (n - 1) / 2);

Embora não seja recursivo na cauda , este algoritmo pode ser reescrito em um algoritmo recursivo na cauda introduzindo uma função auxiliar:

  Function exp_by_squaring(x, n)
    return exp_by_squaring2(1, x, n)
  Function exp_by_squaring2(y, x, n)
    if n < 0  then return exp_by_squaring2(y, 1 / x, - n);
    else if n = 0  then return  y;
    else if n = 1  then return  x * y;
    else if n is even  then return exp_by_squaring2(y, x * x,  n / 2);
    else if n is odd  then return exp_by_squaring2(x * y, x * x, (n - 1) / 2).

Uma variante recursiva de cauda também pode ser construída usando um par de acumuladores em vez de uma função auxiliar, como visto no exemplo F # abaixo. Os acumuladores a1 e a2 podem ser pensados ​​como armazenando os valores e onde i e j são inicializados para 1 e 0, respectivamente. No caso par, i é duplicado e, no caso ímpar, j é aumentado por i. O resultado final é onde . ${\ displaystyle x ^ {i}}$${\ displaystyle x ^ {j}}$${\ displaystyle x ^ {i + j}}$${\ displaystyle i + j = n}$

let exp_by_squaring x n =
    let rec _exp x n' a1 a2 =
        if   n' = 0   then 1
        elif n' = 1   then a1*a2
        elif n'%2 = 0 then _exp x (n'/2) (a1*a1) a2
        else               _exp x (n'-1) a1 (a1*a2)
    _exp x n x 1

A versão iterativa do algoritmo também usa um espaço auxiliar limitado, e é dada por

  Function exp_by_squaring_iterative(x, n)
    if n < 0 then
      x := 1 / x;
      n := -n;
    if n = 0 then return 1
    y := 1;
    while n > 1 do
      if n is even then 
        x := x * x;
        n := n / 2;
      else
        y := x * y;
        x := x * x;
        n := (n - 1) / 2;
    return x * y

Complexidade computacional

Uma breve análise mostra que tal algoritmo usa quadrados e no máximo multiplicações, onde denota a função de piso . Mais precisamente, o número de multiplicações é um a menos que o número de unidades presentes na expansão binária de n . Para n maior do que cerca de 4, isso é computacionalmente mais eficiente do que ingenuamente multiplicar a base com ela mesma repetidamente. ${\ displaystyle \ lfloor \ log _ {2} n \ rfloor}$${\ displaystyle \ lfloor \ log _ {2} n \ rfloor}$${\ displaystyle \ lfloor \; \ rfloor}$

Cada quadratura resulta em aproximadamente o dobro do número de dígitos do anterior e, portanto, se a multiplicação de dois números d- dígitos for implementada em O ( d ^k ) operações para algum k fixo , então a complexidade do cálculo de x ⁿ é dada por

${\ displaystyle \ sum \ limits _ {i = 0} ^ {O (\ log n)} {\ big (} 2 ^ {i} O (\ log x) {\ big)} ^ {k} = O { \ big (} (n \ log x) ^ {k} {\ big)}.}$

Método 2 ^k -ary

Este algoritmo calcula o valor de x ⁿ após expandir o expoente na base 2 ^k . Foi proposto pela primeira vez por Brauer em 1939. No algoritmo abaixo, fazemos uso da seguinte função f (0) = ( k , 0) ef ( m ) = ( s ,  u ), onde m = u · 2 ^s com você é estranho.

Algoritmo:

Entrada

Um elemento x de G , um parâmetro k > 0, um inteiro não negativo n = ( n _{l −1} , n _{l −2} , ..., n ₀ ) _{2 ^k} e os valores pré-calculados .${\ displaystyle x ^ {3}, x ^ {5}, ..., x ^ {2 ^ {k} -1}}$

Saída

O elemento x ⁿ em G

y := 1; i := l - 1
while i ≥ 0 do
    (s, u) := f(ni)
    for j := 1 to k - s do
        y := y2 
    y := y * xu
    for j := 1 to s do
        y := y2
    i := i - 1
return y

Para eficiência ideal, k deve ser o menor inteiro satisfatório

${\ displaystyle \ log n <{\ frac {k (k + 1) \ cdot 2 ^ {2k}} {2 ^ {k + 1} -k-2}} + 1.}$

Método de janela deslizante

Este método é uma variante eficiente do método 2 ^k -ary. Por exemplo, para calcular o expoente 398, que tem expansão binária (110 001 110) ₂ , pegamos uma janela de comprimento 3 usando o algoritmo do método 2 ^k -ary e calculamos 1, x ³ , x ⁶ , x ¹² , x ²⁴ , x ⁴⁸ , x ⁴⁹ , x ⁹⁸ , x ⁹⁹ , x ¹⁹⁸ , x ¹⁹⁹ , x ³⁹⁸ . Mas, também podemos calcular 1, x ³ , x ⁶ , x ¹² , x ²⁴ , x ⁴⁸ , x ⁹⁶ , x ¹⁹² , x ¹⁹⁹ , x ³⁹⁸ , o que economiza uma multiplicação e equivale a avaliar (110 001 110) ₂

Aqui está o algoritmo geral:

Algoritmo:

Entrada

Um elemento x de G , um inteiro não negativo n = ( n _{l −1} , n _{l −2} , ..., n ₀ ) ₂ , um parâmetro k > 0 e os valores pré-calculados .${\ displaystyle x ^ {3}, x ^ {5}, ..., x ^ {2 ^ {k} -1}}$

Saída

O elemento x ⁿ ∈ L .

Algoritmo:

y := 1; i := l - 1
while i > -1 do
    if ni = 0 then
        yy:= y2' i := i - 1
    else
        ss:= max{i - k + 1, 0}
        while ns = 0 do
            ss:= s + 1
        for h := 1 to i - s + 1 do
            yy:= y2
        uu:= (ni, ni-1, ..., ns)2
        yy:= y * xu
        ii:= s - 1
return y

Técnica da escada de Montgomery

Muitos algoritmos de exponenciação não fornecem defesa contra ataques de canal lateral . Ou seja, um invasor observando a sequência de quadrados e multiplicações pode (parcialmente) recuperar o expoente envolvido no cálculo. Isso é um problema se o expoente permanecer secreto, como acontece com muitos sistemas criptográficos de chave pública . Uma técnica chamada " escada de Montgomery " trata dessa preocupação.

Dada a expansão binária de um inteiro positivo diferente de zero n = ( n _{k −1} ... n ₀ ) ₂ com n _{k − 1} = 1, podemos calcular x ^{n da} seguinte forma:

x1 = x; x2 = x2
for i = k - 2 to 0 do
    If ni = 0 then
        x2 = x1 * x2; x1 = x12
    else
        x1 = x1 * x2; x2 = x22
return x1

O algoritmo executa uma sequência fixa de operações ( até log  n ): uma multiplicação e quadratura ocorre para cada bit no expoente, independentemente do valor específico do bit. Existe um algoritmo semelhante para multiplicação por duplicação.

Essa implementação específica da escada de Montgomery ainda não está protegida contra ataques de temporização de cache : as latências de acesso à memória ainda podem ser observadas por um invasor, pois diferentes variáveis ​​são acessadas dependendo do valor dos bits do expoente secreto. As implementações criptográficas modernas usam uma técnica de "dispersão" para garantir que o processador sempre perca o cache mais rápido.

Expoente de base fixa

Existem vários métodos que podem ser empregados para calcular x ⁿ quando a base é fixa e o expoente varia. Como se pode ver, os pré-computações desempenham um papel fundamental nesses algoritmos.

Método de Yao

O método de Yao é ortogonal ao método 2 ^k -ary, onde o expoente é expandido na raiz b = 2 ^k e o cálculo é realizado no algoritmo acima. Sejam n , n _i , b e b _i inteiros.

Deixe o expoente n ser escrito como

${\ displaystyle n = \ sum _ {i = 0} ^ {w-1} n_ {i} b_ {i},}$

onde para todos . ${\ displaystyle 0 \ leqslant n_ {i} <h}$${\ displaystyle i \ in [0, w-1]}$

Seja x _i = x ^{b _i} .

Então o algoritmo usa a igualdade

${\ displaystyle x ^ {n} = \ prod _ {i = 0} ^ {w-1} x_ {i} ^ {n_ {i}} = \ prod _ {j = 1} ^ {h-1} { \ bigg [} \ prod _ {n_ {i} = j} x_ {i} {\ bigg]} ^ {j}.}$

Dado o elemento x de G e o expoente n escrito na forma acima, junto com os valores pré-computados x ^{b ₀} ... x ^{b _{w −1}} , o elemento x ⁿ é calculado usando o algoritmo abaixo:

y = 1, u = 1, j = h - 1
while j > 0 do
    for i = 0 to w - 1 do
        if ni = j then
            u = u × xbi
    y = y × u
    j = j - 1
return y

Se definirmos h = 2 ^k e b _i = h ⁱ , então os valores de n _i são simplesmente os dígitos de n na base h . O método de Yao coleta em u primeiro aqueles x _i que aparecem na maior potência ; na próxima rodada aqueles com poder são coletados em u também etc. A variável y é multiplicada vezes com o u inicial , vezes com os próximos poderes mais altos, e assim por diante. O algoritmo usa multiplicações e os elementos devem ser armazenados para calcular x ⁿ . ${\ displaystyle h-1}$${\ displaystyle h-2}$${\ displaystyle h-1}$${\ displaystyle h-2}$${\ displaystyle w + h-2}$${\ displaystyle w + 1}$

Método euclidiano

O método euclidiano foi introduzido pela primeira vez na exponenciação eficiente usando cadeias de pré-computação e adição de vetores por PD Rooij.

Este método para calcular no grupo G , onde n é um inteiro natural, cujo algoritmo é dado abaixo, está usando a seguinte igualdade recursivamente: ${\ displaystyle x ^ {n}}$

${\ displaystyle x_ {0} ^ {n_ {0}} \ cdot x_ {1} ^ {n_ {1}} = \ left (x_ {0} \ cdot x_ {1} ^ {q} \ right) ^ { n_ {0}} \ cdot x_ {1} ^ {n_ {1} \ mod n_ {0}},}$

onde . Em outras palavras, uma divisão euclidiana do expoente n ₁ por n ₀ é usada para retornar um quociente qe um resto n ₁ mod n ₀ . ${\ displaystyle q = \ left \ lfloor {\ frac {n_ {1}} {n_ {0}}} \ right \ rfloor}$

Dado o elemento de base x no grupo G e o expoente escrito como no método de Yao, o elemento é calculado usando valores pré- calculados e, em seguida, o algoritmo abaixo. ${\ displaystyle n}$${\ displaystyle x ^ {n}}$${\ displaystyle l}$${\ displaystyle x ^ {b_ {0}}, ..., x ^ {b_ {l_ {i}}}}$

Begin loop   
    Find ${\displaystyle M\in [0,l-1]}$, such that ${\displaystyle \forall i\in [0,l-1],n_{M}\geq n_{i}}$.
    Find ${\displaystyle N\in {\big (}[0,l-1]-M{\big )}}$, such that ${\displaystyle \forall i\in {\big (}[0,l-1]-M{\big )},n_{N}\geq n_{i}}$.
    Break loop if ${\displaystyle n_{N}=0}$.
    Let ${\displaystyle q=\lfloor n_{M}/n_{N}\rfloor }$, and then let ${\displaystyle n_{N}=(n_{M}{\bmod {n}}_{N})}$.
    Compute recursively ${\displaystyle x_{M}^{q}}$, and then let ${\displaystyle x_{N}=x_{N}\cdot x_{M}^{q}}$.
End loop;
Return ${\displaystyle x^{n}=x_{M}^{n_{M}}}$.

O algoritmo primeiro encontra o maior valor entre os n _i e, em seguida, o supremo dentro do conjunto de { n _i \ i ≠ M } . Em seguida, ele levanta x _M para o poder q , multiplica-se este valor com X _N , e em seguida, atribui x _N o resultado deste cálculo e n _H o valor n _M módulo n _N .

Outras aplicações

A mesma ideia permite o cálculo rápido de expoentes grandes modulo um número. Especialmente em criptografia , é útil para calcular potências em um anel de inteiros módulo q . Também pode ser usado para calcular potências inteiras em um grupo , usando a regra

Potência ( x , - n ) = (Potência ( x , n )) ⁻¹ .

O método funciona em todos os semigrupos e é freqüentemente usado para calcular potências de matrizes .

Por exemplo, a avaliação de

13789 ⁷²²³⁴¹ (mod 2345) = 2029

levaria muito tempo e muito espaço de armazenamento se o método ingênuo fosse usado: calcule 13789 ⁷²²³⁴¹ , então pegue o resto quando dividido por 2345. Mesmo usando um método mais eficaz levará muito tempo: quadrado 13789, pegue o resto quando dividido por 2345, multiplique o resultado por 13789 e assim por diante. Isso levará menos do que multiplicações modulares. ${\ displaystyle 2 \ log _ {2} (722340) \ leq 40}$

Aplicar o algoritmo exp-por-quadrado acima , com "*" interpretado como x  *  y = xy mod 2345 (ou seja, uma multiplicação seguida por uma divisão com resto) leva a apenas 27 multiplicações e divisões de inteiros, que podem ser todos armazenados em uma única palavra de máquina.

Recodificação de dígitos assinados

Em certos cálculos, pode ser mais eficiente permitir coeficientes negativos e, portanto, usar o inverso da base, desde que a inversão em G seja "rápida" ou tenha sido pré-calculada. Por exemplo, ao calcular x ^{2 k −1} , o método binário requer k −1 multiplicações e k −1 quadrados. No entanto, pode-se realizar k quadrados para obter x ^{2 k} e depois multiplicar por x ⁻¹ para obter x ^{2 k −1} .

Para este fim, definimos a representação de dígitos com sinais de um inteiro n na raiz b como

${\ displaystyle n = \ sum _ {i = 0} ^ {l-1} n_ {i} b ^ {i} {\ text {with}} | n_ {i} | <b.}$

A representação binária com sinal corresponde à escolha particular b = 2 e . É denotado por . Existem vários métodos para calcular esta representação. A representação não é única. Por exemplo, tome n = 478 : duas representações binárias com sinal distintas são fornecidas por e , onde é usado para denotar −1 . Uma vez que o método binário calcula uma multiplicação para cada entrada diferente de zero na representação de base 2 de n , estamos interessados ​​em encontrar a representação binária com sinal com o menor número de entradas diferentes de zero, ou seja, aquela com o mínimo de Hamming peso . Um método de fazer isso é calcular a representação na forma não adjacente , ou NAF, abreviadamente, que é aquele que satisfaz e é denotado por . Por exemplo, a representação NAF de 478 é . Essa representação sempre tem peso de Hamming mínimo. Um simples algoritmo para calcular a representação NAF de um determinado número inteiro com é o seguinte: ${\ displaystyle n_ {i} \ in \ {- 1,0,1 \}}$${\ displaystyle (n_ {l-1} \ dots n_ {0}) _ {s}}$${\ displaystyle (10 {\ bar {1}} 1100 {\ bar {1}} 10) _ {s}}$${\ displaystyle (100 {\ bar {1}} 1000 {\ bar {1}} 0) _ {s}}$${\ displaystyle {\ bar {1}}}$ ${\ displaystyle n_ {i} n_ {i + 1} = 0 {\ text {para todos}} i \ geqslant 0}$${\ displaystyle (n_ {l-1} \ dots n_ {0}) _ {\ text {NAF}}}$${\ displaystyle (1000 {\ bar {1}} 000 {\ bar {1}} 0) _ {\ text {NAF}}}$${\ displaystyle n = (n_ {l} n_ {l-1} \ pontos n_ {0}) _ {2}}$${\ displaystyle n_ {l} = n_ {l-1} = 0}$

${\displaystyle c_{0}=0}$
for i = 0 to l − 1 do
  ${\displaystyle c_{i+1}=\left\lfloor {\frac {1}{2}}(c_{i}+n_{i}+n_{i+1})\right\rfloor }$
  ${\displaystyle n_{i}'=c_{i}+n_{i}-2c_{i+1}}$
return ${\displaystyle (n_{l-1}'\dots n_{0}')_{\text{NAF}}}$

Outro algoritmo de Koyama e Tsuruoka não requer a condição de que ; ainda minimiza o peso de Hamming. ${\ displaystyle n_ {i} = n_ {i + 1} = 0}$

Alternativas e generalizações

A exponenciação por quadratura pode ser vista como um algoritmo de exponenciação de cadeia de adição subótimo : ele calcula o expoente por uma cadeia de adição que consiste em duplicações de expoentes repetidas (quadraturas) e / ou expoentes incrementais por um (multiplicando por x ) apenas. Mais geralmente, se alguém permite que quaisquer expoentes calculados anteriormente sejam somados (multiplicando essas potências de x ), pode-se às vezes realizar a exponenciação usando menos multiplicações (mas normalmente usando mais memória). A menor potência onde isso ocorre é para n = 15:

${\ displaystyle x ^ {15} = x \ times (x \ times [x \ times x ^ {2}] ^ {2}) ^ {2}}$ (ao quadrado, 6 multiplicações),

${\ displaystyle x ^ {15} = x ^ {3} \ times ([x ^ {3}] ^ {2}) ^ {2}}$ (cadeia de adição ótima, 5 multiplica se x ³ for reutilizado).

Em geral, encontrar a cadeia de adição ideal para um determinado expoente é um problema difícil, para o qual nenhum algoritmo eficiente é conhecido, então cadeias ótimas são normalmente usadas apenas para expoentes pequenos (por exemplo, em compiladores onde as cadeias para potências pequenas foram pré-tabuladas ) No entanto, há vários algoritmos heurísticos que, embora não sejam ideais, têm menos multiplicações do que exponenciação ao elevar ao quadrado ao custo de trabalho de contabilidade adicional e uso de memória. Independentemente disso, o número de multiplicações nunca cresce mais lentamente do que Θ (log n ), de modo que esses algoritmos só melhoram assintoticamente após a exponenciação ao elevar ao quadrado por um fator constante, na melhor das hipóteses.

Veja também

• Exponenciação modular
• Cadeia de adição vetorial
• Redução de Montgomery
• Forma não adjacente
• Cadeia de adição

Notas

Referências