Exponenciação ao quadrado

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Algoritmo para exponencialização rápida

Em matemática e programação de computadores, exponenciar por quadratura é 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 um matriz quadrada. Algumas variantes são comumente chamadas de algoritmos quadrado e multiplicado 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ípticas usadas em criptografia, esse método também é conhecido como duplo e adição.

Método básico

Versão recursiva

O método é baseado na observação que, para qualquer inteiro $0}" xmlns="http://www.w3.org/1998/Math/MathML">n>0- Sim. 0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/27a6a5d982d54202a14f111cb8a49210501b2c96" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;"/>$ , um tem:

{displaystyle x^{n}={begin{cases}x,(x^{2})^{(n-1)/2},&{mbox{if }}n{mbox{ is odd}}\(x^{2})^{n/2},&{mbox{if }}n{mbox{ is even}}end{cases}}}

Se o expoente for zero, a resposta é 1 e, se o expoente for negativo, podemos reutilizar a fórmula anterior reescrevendo o valor usando um expoente positivo. Aquilo é,

{displaystyle x^{-n}=left({frac {1}{x}}right)^{n},.}

Juntos, eles podem ser implementados diretamente como o seguinte algoritmo recursivo:

 In: an integer x; an integer n
Fora: xⁿexp_by_squaring(x, n)
se n < 0 então
retornar exp_by_squaring(1 / x, -n);
mais se n = 0 então
devolução 1;
mais se n é mesmo então
retornar exp_by_squaring(x * x, n / 2);
então se n é estranho
retornar x * exp_by_squaring(x * x, (n - 1) / 2);
função final

Em cada chamada recursiva, os dígitos menos significativos da representação binária de $n$ é removido. Segue-se que o número de chamadas recursivas é ${displaystyle lceil log _{2}nrceil}$ o número de bits da representação binária de $n$ . Então este algoritmo computa esse número de quadrados e um número menor de multiplicação, que é igual ao número de $1$ na representação binária de $n$ . Este número logarítmico de operações deve ser comparado com o algoritmo trivial que requer $n - 1$ multiplicações.

Este algoritmo não é recursivo na cauda. Isso implica que requer uma memória auxiliar aproximadamente proporcional (ou superior, se levarmos em conta o tamanho crescente dos dados) ao número de chamadas recursivas.

Os algoritmos da próxima seção usam uma abordagem diferente, e os algoritmos resultantes precisam do mesmo número de operações, mas usam uma memória auxiliar que é aproximadamente a mesma que a memória necessária para armazenar o resultado.

Com memória auxiliar constante

As variantes descritas nesta seção são baseadas na fórmula

{displaystyle yx^{n}={begin{cases}(yx),(x^{2})^{(n-1)/2},&{mbox{if }}n{mbox{ is odd}}\y,(x^{2})^{n/2},&{mbox{if }}n{mbox{ is even}}.end{cases}}}

Aplicando recursivamente esta fórmula, começando com $y = 1$ , obtém-se eventualmente um expoente igual a $0$ , e o resultado desejado é então o fator esquerdo.

Isso pode ser implementado como uma função recursiva de cauda:

 Função exp_by_squarting(x, n) retorno exp_by_squaring2(1, x, n) Função exp_by_squaring2(Sim., x, n) se n < 0 então retorno exp_by_squaring2(Sim., 1 / x, - Não. n); mais se n = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 0 então retorno Sim.; mais se n o mesmo então retorno exp_by_squaring2(Sim., x * x, n / 2); mais se n o O quê? então retorno exp_by_squaring2(x * Sim., x * x, (n - Não. 1) / 2).

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

 Função exp_by_squaring_iterative(x, n) se n < 0 então x ? 1 / x; n ? - Não.n; se n = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 0 então retorno 1 Sim. ? 1; enquanto n > 1 do se n o mesmo então x ? x * x; n ? n / 2; mais Sim. ? x * Sim.; x ? x * x; n ? (n – 1) / 2; retorno x * Sim.

A correção do algoritmo resulta do fato de que ${displaystyle yx^{n}}$ é invariante durante a computação; é ${displaystyle 1cdot x^{n}=x^{n}}$ no início; e é ${displaystyle yx^{0}=y}$ no fim.

Esses algoritmos usam exatamente o mesmo número de operações que o algoritmo da seção anterior, mas as multiplicações são feitas em uma ordem diferente.

Complexidade computacional

Uma breve análise mostra que tal algoritmo usa $lfloor log _{2}nrfloor$ squarings e no máximo $lfloor log _{2}nrfloor$ multiplicações, onde $lfloor ;rfloor$ denota a função de piso. Mais precisamente, o número de multiplicações é um menos do que o número de presentes na expansão binária de n. Para n maior do que cerca de 4 isto é computacionalmente mais eficiente do que ingênuo multiplicando a base com si mesmo repetidamente.

Cada quadrado resulta em aproximadamente o dobro do número de dígitos do anterior, e assim, se a multiplicação de dois números de d dígitos for implementada em O(d^k) para alguns k fixos, então a complexidade da computação xⁿ é dado por

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

Método 2k-ário

Este algoritmo calcula o valor de xⁿ depois de expandir o expoente na base 2^k. Foi proposto pela primeira vez por Brauer em 1939. No algoritmo abaixo, usamos a seguinte função f(0) = (k,0) e f(m) = (s,u), onde m = u·2^s com u ímpar.

Algoritmo:

Entrada: Um elemento x de G, um parâmetro k > 0, um inteiro não negativo $n Não. n Eu... - Sim., n Eu... -2, n 0) 2 k$ e os valores pré-computados $x^{3},x^{5},...,x^{2^{k}-1}$ .

Saída: O elemento xⁿ em G

I:= 1, i:= l - 1
enquanto i ≥ 0 do
(s)_Eu...)
 para O quê? 1 para k - s doSim. Sim.²Sim.^u para O quê? 1 para S doSim. Sim.²Eu... I - 1
retorno Sim.

Para eficiência ideal, k deve ser o menor número inteiro que satisfaça

<math alttext="{displaystyle log nlog⁡ ⁡ n<k(k+1))) 22k2k+1- Sim. - Sim. k- Sim. - Sim. 2+1.{displaystyle log n<{frac {k(k+1)cdot 2^{2k}}{2^{k+1}-k-2}}+1.}<img alt="{displaystyle log n

Método de janela deslizante

Este método é uma variante eficiente do método 2^k-ário. Por exemplo, para calcular o expoente 398, que tem expansão binária (110 001 110)₂, tomamos uma janela de comprimento 3 usando o 2^{k-ário e calcule 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³⁹⁸, que salva 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ão. n Eu... - Sim., n Eu... -2, n 0) 2$ , um parâmetro k > 0 e os valores pré-computados $x^{3},x^{5},...,x^{2^{k}-1}$ .

Saída: O elemento xⁿ ∈ G.

Algoritmo:

I:= 1, i:= l - 1
enquanto I > do se n_Eu... = 0 entãoSim. Sim.²Eu... I - 1
 maisO quê? max{i - k + 1, 0}
 enquanto n_S = 0 do:
 para Não. 1 para i - s + 1 doSim. Sim.²:_Eu...,_Eu...,_S)₂Sim.^u:
retorno Sim.

Técnica da escada de Montgomery

Muitos algoritmos para exponenciação não fornecem defesa contra ataques de canal lateral. Ou seja, um invasor observando a sequência de quadraturas e multiplicações pode (parcialmente) recuperar o expoente envolvido na computação. Isso é um problema se o expoente deve 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ⁿ da seguinte forma:

x₁ = x; x₂ = x²para i = k - 2 a 0 do se n_Eu... = 0 entãox₂ = x₁ * x₂; x₁ = x₁² maisx₁ = x₁ * x₂; x₂ = x₂²retorno x₁

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

Esta 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 observáveis para um invasor, pois diferentes variáveis são acessadas dependendo do valor dos bits do expoente secreto. As implementações criptográficas modernas usam um padrão de "dispersão" técnica 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, 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 em radix $b = 2 k$ e o cálculo é feito conforme o algoritmo acima. Deixe $n$ , $n i$ , $b$ e $b i$ ser números inteiros.

Deixe o expoente $n$ ser escrito como

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

Onde? $<math alttext="{displaystyle 0leqslant n_{i}0⩽ ⩽ nEu...<h{displaystyle 0leqslant N_{i}<h}<img alt="{displaystyle 0leqslant n_{i}$ para todos ${displaystyle iin [0,w-1]}$ .

Seja $x i = x b i$ .

Em seguida, 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é-calculados $x b 0 ... x b w -1$ , o elemento $x n$ é calculado usando o algoritmo abaixo:

y = 1, u = 1, j = h - 1
enquanto J > 0 do para I = 0 para 1 do se n_Eu... - Sim. entãou = u x x^b)_Eu...y × u
J = j - 1
retorno Sim.

Se definirmos $h = 2 k$ e $b) Eu... = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = h Eu...$ , então o $n Eu...$ valores são simplesmente os dígitos de $n$ em base $h$ . Método de Yao coleta em u primeiro aqueles $x Eu...$ que aparecem ao mais alto poder ${displaystyle h-1}$ ; na próxima rodada aqueles com poder ${displaystyle h-2}$ são coletadas em $u$ bem etc. A variável Sim. é multiplicado ${displaystyle h-1}$ tempos com a inicial $u$ , ${displaystyle h-2}$ tempos com os próximos mais altos poderes, e assim por diante. O algoritmo usa ${displaystyle w+h-2}$ multiplicações, e ${displaystyle w+1}$ elementos devem ser armazenados em computação $x n$ .

Método euclidiano

O método euclidiano foi introduzido pela primeira vez em Exponenciação eficiente usando pré-computação e cadeias de adição de vetores por P.D Rooij.

Este método para computação $x^{n}$ em grupo $G$ , onde $n$ é um inteiro natural, cujo algoritmo é dado abaixo, está usando a seguinte igualdade recursivamente:

{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? ${displaystyle q=leftlfloor {frac {n_{1}}{n_{0}}}rightrfloor }$ . Em outras palavras, uma divisão euclidiana do expoente $n 1$ por $n 0$ é usado para retornar um quociente $q$ e um descanso $n 1 mod n 0$ .

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

Iniciar loop Encontrar  ${displaystyle Min [0,l-1]}$ , tal que  ${displaystyle forall iin [0,l-1],n_{M}geq n_{i}}$ . Encontrar  ${displaystyle Nin {big (}[0,l-1]-M{big)}}$ , tal que  ${displaystyle forall iin {big (}[0,l-1]-M{big)},n_{N}geq n_{i}}$ . loop de ruptura se  ${displaystyle n_{N}=0}$ . Vamos.  ${displaystyle q=lfloor n_{M}/n_{N}rfloor }$ , e depois Deixa-me.  ${displaystyle n_{N}=(n_{M}{bmod {n}}_{N})}$ . Compute recursivamente  ${displaystyle x_{M}^{q}}$ , e depois Deixa-me.  ${displaystyle x_{N}=x_{N}cdot x_{M}^{q}}$ .loop final;
Voltar  ${displaystyle x^{n}=x_{M}^{n_{M}}}$ .

O algoritmo primeiro encontra o maior valor entre os $n i$ e depois os supremo dentro do conjunto de ${n i i \neq M}$ . Em seguida, eleva $x M$ à potência $q$ , multiplica este valor por $x N$ e, em seguida, atribui $x N$ o resultado desse cálculo e $n M$ o valor $n M$ módulo $n N$ .

Aplicações adicionais

A mesma ideia permite o cálculo rápido de grandes expoentes módulo um número. Especialmente em criptografia, é útil 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

Poder(x,n) = (Poder(x, n)^{- Sim.}.

O método funciona em todos os semigrupos e é frequentemente 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: computa 13789⁷²²³, então tomar o restante quando dividido por 2345. Mesmo usando um método mais eficaz vai demorar muito tempo: quadrado 13789, tomar o restante quando dividido por 2345, multiplicar o resultado por 13789, e assim por diante. Isto levará menos do que ${displaystyle 2log _{2}(722340)leq 40}$ multiplicações modulares.

Aplicando o algoritmo exp-by-squaring 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 números inteiros, que podem ser 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$ é "rápido" ou foi pré-computado. Por exemplo, ao calcular $x 2 k -1$ , o método binário requer $k -1$ multiplicações e $k -1$ quadraturas. No entanto, pode-se executar $k$ quadrados para obter $x 2 k$ e então multiplique por $x -1$ para obter $x 2 k -1$ .

Para esse fim, definimos a representação de dígitos assinados de um inteiro $n$ na raiz $b$ como

<math alttext="{displaystyle n=sum _{i=0}^{l-1}n_{i}b^{i}{text{ with }}|n_{i}|n= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =Gerenciamento Gerenciamento Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0Eu...- Sim. - Sim. 1nEu...b)Eu...com|nEu...|<b).{displaystyle n=sum _{i=0}^{l-1}n_{i}b^{i}{text{ with }}|n_{i}|<b.}<img alt="{displaystyle n=sum _{i=0}^{l-1}n_{i}b^{i}{text{ with }}|n_{i}|

Representação binária assinada corresponde à escolha específica $b) = 2$ e ${displaystyle n_{i}in {-1,0,1}}$ . É denotado por ${displaystyle (n_{l-1}dots n_{0})_{s}}$ . Existem vários métodos para computar esta representação. A representação não é única. Por exemplo, tome $n = 478$ : são dadas duas representações distintas de ligação assinado $(10{bar {1}}1100{bar {1}}10)_{s}$ e $(100{bar {1}}1000{bar {1}}0)_{s}$ , onde ${bar {1}}$ é usado para denotar $- Sim.$ . Uma vez que o método binário computa uma multiplicação para cada entrada não-zero na representação base-2 da $n$ , estamos interessados em encontrar a representação binária assinada com o menor número de entradas não-zero, ou seja, aquele com mínimo Peso de Hamming. Um método de fazer isso é computar a representação em forma não adjacente, ou NAF para curto, que é um que satisfaz ${displaystyle n_{i}n_{i+1}=0{text{ for all }}igeqslant 0}$ e denotado por ${displaystyle (n_{l-1}dots n_{0})_{text{NAF}}}$ . Por exemplo, a representação NAF de 478 é ${displaystyle (1000{bar {1}}000{bar {1}}0)_{text{NAF}}}$ . Esta representação sempre tem peso mínimo Hamming. Um algoritmo simples para calcular a representação NAF de um determinado inteiro ${displaystyle n=(n_{l}n_{l-1}dots n_{0})_{2}}$ com ${displaystyle n_{l}=n_{l-1}=0}$ é o seguinte:

 $c_{0}=0$ para  $Eu... = 0$  para  $Eu... - 1$  do
  ${displaystyle c_{i+1}=leftlfloor {frac {1}{2}}(c_{i}+n_{i}+n_{i+1})rightrfloor }$   ${displaystyle n_{i}'=c_{i}+n_{i}-2c_{i+1}}$ retorno  ${displaystyle (n_{l-1}'dots n_{0}')_{text{NAF}}}$

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

Alternativas e generalizações

A exponenciação por quadratura pode ser vista como um algoritmo de exponenciação de cadeia de adição abaixo do ideal: ele calcula o expoente por uma cadeia de adição que consiste em duplicações repetidas de expoentes (quadraturas) e/ou incremento de expoentes por um (multiplicando por x) apenas. De forma mais geral, se permitirmos que quaisquer expoentes calculados anteriormente sejam somados (multiplicando essas potências de x), às vezes é possível 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}=xtimes (xtimes [xtimes x^{2}]^{2})^{2}}$ (quarto, 6 multiplica),

${displaystyle x^{15}=x^{3}times ([x^{3}]^{2})^{2}}$ (corrente de adição ideal, 5 multiplica se x³ é reutilizado).

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

Más resultados...