Exponenciação modular - Modular exponentiation

A exponenciação modular é um tipo de exponenciação realizada sobre um módulo . É útil em ciência da computação , especialmente no campo da criptografia de chave pública .

A operação de exponenciação modular calcula o restante quando um número inteiro b (a base) levantada para o e po de energia (o expoente), b ^e , é modulada ao longo de um número inteiro positivo m (o módulo). Em símbolos, dada a base b , expoente ee módulo m , a exponenciação modular c é: c = b ^e mod m . Da definição de c , segue-se que 0 ≤ c < m .

Por exemplo, dado b = 5 , e = 3 e m = 13 , a solução c = 8 é o resto da modulação de 5 ³ = 125 sobre 13 .

Exponenciação modular pode ser realizada com um negativo expoente e encontrando a modular multiplicativo inverso d de b módulo m utilizando o algoritmo de Euclides estendida . Isso é:

c = b ^e mod m = d ^{- e} mod m , onde e <0 e b ⋅ d ≡ 1 (mod m ) .

A exponenciação modular semelhante à descrita acima é considerada fácil de calcular, mesmo quando os inteiros envolvidos são enormes. Por outro lado, o cálculo do logaritmo discreto modular - isto é, a tarefa de encontrar o expoente e quando dado b , c e m - é considerado difícil. Este comportamento de função unilateral torna a exponenciação modular um candidato para uso em algoritmos criptográficos.

Método direto

O método mais direto de calcular um expoente modular é calcular b ^e diretamente ^e , a seguir, tomar esse número módulo m . Considere tentar calcular c , dado b = 4 , e = 13 e m = 497 :

c ≡ 4 ¹³ (mod 497)

Pode-se usar uma calculadora para calcular 4 ¹³ ; isso dá 67.108.864. Tomando este valor módulo 497, a resposta c é determinada como 445.

Observe que b tem apenas um dígito de comprimento e que e tem apenas dois dígitos, mas o valor b ^e tem 8 dígitos.

Na criptografia forte, b geralmente tem pelo menos 1024 bits . Considere b = 5 × 10 ⁷⁶ e e = 17 , sendo que ambos são valores perfeitamente razoáveis. Neste exemplo, b tem 77 dígitos de comprimento e e tem 2 dígitos de comprimento, mas o valor b ^e tem 1.304 dígitos decimais de comprimento. Esses cálculos são possíveis em computadores modernos, mas a magnitude desses números faz com que a velocidade dos cálculos diminua consideravelmente. À medida que b e e aumentam ainda mais para fornecer melhor segurança, o valor b ^e torna-se pesado.

O tempo necessário para realizar a exponenciação depende do ambiente operacional e do processador. O método descrito acima requer multiplicações O ( e ) para ser concluído.

Método eficiente de memória

Manter os números menores requer operações adicionais de redução modular, mas o tamanho reduzido torna cada operação mais rápida, economizando tempo (bem como memória) em geral.

Este algoritmo faz uso da identidade

( a ⋅ b ) mod m = [( a mod m ) ⋅ ( b mod m )] mod m

O algoritmo modificado é:

1. Defina c = 1 , e ′ = 0 .
2. Aumente e ′ em 1.
3. Defina c = (b ⋅ c) mod m .
4. Se e ′ < e , vá para a etapa 2. Do contrário, c contém a solução correta para c ≡ b ^e (mod m ) .

Observe que em cada passagem pela etapa 3, a equação c ≡ b ^{e ′} (mod m ) é verdadeira. Quando o passo 3 foi executado e vezes, então, c contém a resposta que foi buscada. Em resumo, esse algoritmo basicamente conta e ′ por unidades até que e ′ alcance e , fazendo a multiplicação por be uma operação de módulo cada vez que adiciona um (para garantir que os resultados permaneçam pequenos).

O exemplo b = 4 , e = 13 e m = 497 é apresentado novamente. O algoritmo passa pela etapa 3 treze vezes:

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

A resposta final para c é, portanto, 445, como no primeiro método.

Como o primeiro método, isso requer multiplicações O ( e ) para ser concluído. No entanto, como os números usados ​​nesses cálculos são muito menores do que os números usados ​​nos cálculos do primeiro algoritmo, o tempo de cálculo diminui por um fator de pelo menos O ( e ) neste método.

Em pseudocódigo, este método pode ser executado da seguinte maneira:

function modular_pow(base, exponent, modulus) is
    if modulus = 1 then
        return 0
    c := 1
    for e_prime = 0 to exponent-1 do
        c := (c * base) mod modulus
    return c

Método binário da direita para a esquerda

Um terceiro método reduz drasticamente o número de operações para realizar a exponenciação modular, enquanto mantém a mesma área de cobertura de memória do método anterior. É uma combinação do método anterior e um princípio mais geral denominado exponenciação por quadratura (também conhecida como exponenciação binária ).

Primeiro, é necessário que o expoente e seja convertido para notação binária . Ou seja, e pode ser escrito como:

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

Nessa notação, o comprimento de e é de n bits. a _i pode assumir o valor 0 ou 1 para qualquer i tal que 0 ≤ i < n . Por definição, a _{n - 1} = 1 .

O valor b ^e pode ser escrito como:

${\displaystyle b^{e}=b^{\left(\sum _{i=0}^{n-1}a_{i}2^{i}\right)}=\prod _{i=0}^{n-1}b^{a_{i}2^{i}}}$

A solução c é, portanto:

${\displaystyle c\equiv \prod _{i=0}^{n-1}b^{a_{i}2^{i}}{\pmod {m}}}$

Pseudo-código

O seguinte é um exemplo em pseudocódigo baseado na criptografia aplicada por Bruce Schneier . As entradas base , expoente e módulo correspondem a b , e e m nas equações fornecidas acima.

function modular_pow(base, exponent, modulus) is
    if modulus = 1 then
        return 0
    Assert :: (modulus - 1) * (modulus - 1) does not overflow base
    result := 1
    base := base mod modulus
    while exponent > 0 do
        if (exponent mod 2 == 1) then
            result := (result * base) mod modulus
        exponent := exponent >> 1
        base := (base * base) mod modulus
    return result

Observe que ao entrar no loop pela primeira vez, a variável de código base é equivalente a b . No entanto, o quadrado repetido na terceira linha de código garante que, na conclusão de cada loop, a variável base seja equivalente a b ^{2 i} mod m , onde i é o número de vezes que o loop foi iterado. (Isso torna i o próximo bit de trabalho do expoente do expoente binário , onde o bit menos significativo é o expoente ₀ ).

A primeira linha de código simplesmente realiza a multiplicação em . Se um${\displaystyle \prod _{i=0}^{n-1}b^{a_{i}2^{i}}{\pmod {m}}}$é zero, nenhum código é executado, pois isso efetivamente multiplica o total em execução por um. Se umem vez disso, é um, a base variável (contendo o valor b ^{2 i} mod m da base original) é simplesmente multiplicada em.

Neste exemplo, a base b é elevada ao expoente e = 13 . O expoente é 1101 em binário. Existem quatro dígitos binários, de modo que o laço é executado quatro vezes, com valores de ₀ = 1, um _{de 1} = 0, um ₂ = 1 , e uma ₃ = 1 .

Primeiro, inicialize o resultado como 1 e preserve o valor de b na variável x : ${\displaystyle R}$

${\displaystyle R\leftarrow 1\,(=b^{0}){\text{ and }}x\leftarrow b}$.

Etapa 1) o bit 1 é 1, então defina ; ${\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{1})}$

definido .${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{2})}$

Etapa 2) o bit 2 é 0, portanto, não reinicie R ;

definido .${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{4})}$

Etapa 3) o bit 3 é 1, então defina ; ${\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{5})}$

definido .${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{8})}$

Etapa 4) o bit 4 é 1, então defina ; ${\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{13})}$

Esta é a última etapa, portanto não precisamos elevar x ao quadrado .

Terminamos: R é agora . ${\displaystyle b^{13}}$

Aqui está o cálculo acima, onde computamos b = 4 elevado à potência e = 13 , executado no módulo 497.

Inicializar:

${\displaystyle R\leftarrow 1\,(=b^{0})}$ e .${\displaystyle x\leftarrow b=4}$

Etapa 1) o bit 1 é 1, então defina ; ${\displaystyle R\leftarrow R\cdot 4\equiv 4{\pmod {497}}}$

definido .${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{2})\equiv 4^{2}\equiv 16{\pmod {497}}}$

Etapa 2) o bit 2 é 0, portanto, não reinicie R ;

definido .${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{4})\equiv 16^{2}\equiv 256{\pmod {497}}}$

Etapa 3) o bit 3 é 1, então defina ; ${\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{5})\equiv 4\cdot 256\equiv 30{\pmod {497}}}$

definido .${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{8})\equiv 256^{2}\equiv 429{\pmod {497}}}$

Etapa 4) o bit 4 é 1, então defina ;${\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{13})\equiv 30\cdot 429\equiv 445{\pmod {497}}}$

Terminamos: R é agora , o mesmo resultado obtido nos algoritmos anteriores. ${\displaystyle 4^{13}\equiv 445{\pmod {497}}}$

O tempo de execução desse algoritmo é O (log expoente ) . Ao trabalhar com grandes valores de expoente , isso oferece um benefício de velocidade substancial em relação aos dois algoritmos anteriores, cujo tempo é O ( expoente ) . Por exemplo, se o expoente era 2 ²⁰ = 1048576, esse algoritmo teria 20 etapas em vez de 1048576 etapas.

Implementação em Lua

function modPow(b, e, m)
  if m == 1 then
    return 0
  else
    local r = 1
    b = b % m
    while e > 0 do
      if e % 2 == 1 then
        r = (r*b) % m
      end
      b = (b*b) % m
      e = e >> 1     --use 'e = math.floor(e / 2)' on Lua 5.2 or older
    end
    return r
  end
end

Método binário da esquerda para a direita

Também podemos usar os bits do expoente na ordem da esquerda para a direita. Na prática, normalmente queremos o resultado módulo algum módulo m . Nesse caso, reduziríamos cada resultado da multiplicação (mod m ) antes de prosseguir. Para simplificar, o cálculo do módulo é omitido aqui. Este exemplo mostra como calcular usando a exponenciação binária da esquerda para a direita. O expoente é 1101 em binário; existem 4 bits, portanto, existem 4 iterações. ${\displaystyle b^{13}}$

Inicializar o resultado a 1: . ${\displaystyle r\leftarrow 1\,(=b^{0})}$

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

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

Etapa 3) ; bit 3 = 0, então concluímos esta etapa;${\displaystyle r\leftarrow r^{2}\,(=b^{6})}$

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

Multiplicações mínimas

Em The Art of Computer Programming , vol. 2, Seminumerical Algorithms , página 463, Donald Knuth observa que, ao contrário de algumas afirmações, este método nem sempre dá o número mínimo possível de multiplicações. O menor contra-exemplo é para uma potência de 15, quando o método binário precisa de seis multiplicações. Em vez disso, de forma x ³ em duas multiplicações, então x ⁶ por quadratura x ³ , então x ¹² por quadratura x ⁶ , e finalmente x ¹⁵ multiplicando x ¹² e x ³ , conseguindo-se assim o resultado desejado com apenas cinco multiplicações. No entanto, muitas páginas seguem descrevendo como tais sequências podem ser planejadas em geral.

Generalizações

Matrizes

O m- ésimo termo de qualquer sequência recursiva constante (como números de Fibonacci ou números de Perrin ) onde cada termo é uma função linear de k termos anteriores pode ser calculado de forma eficiente módulo n calculando A ^m mod n , onde A é o k correspondente × k matriz companheira . Os métodos acima se adaptam facilmente a esta aplicação. Isso pode ser usado para teste de primalidade de grandes números n , por exemplo.

Pseudo-código

Um algoritmo recursivo para ModExp(A, b, c)= A ^b mod c , onde A é uma matriz quadrada.

function Matrix_ModExp(Matrix A, int b, int c) is
    if b == 0 then
        return I  // The identity matrix
    if (b mod 2 == 1) then
        return (A * Matrix_ModExp(A, b - 1, c)) mod c
    Matrix D := Matrix_ModExp(A, b / 2, c)
    return (D * D) mod c

Grupos cíclicos finitos

A troca de chaves Diffie – Hellman usa exponenciação em grupos cíclicos finitos. Os métodos acima para exponenciação de matriz modular se estendem claramente a este contexto. A multiplicação da matriz modular C ≡ AB (mod n ) é simplesmente substituída em qualquer lugar pela multiplicação do grupo c = ab .

Exponenciação modular reversível e quântica

Na computação quântica , a exponenciação modular aparece como o gargalo do algoritmo de Shor , onde deve ser calculada por um circuito que consiste em portas reversíveis , que podem ser subdivididas em portas quânticas apropriadas para um dispositivo físico específico. Além disso, no algoritmo de Shor é possível conhecer a base e o módulo de exponenciação a cada chamada, o que permite várias otimizações de circuito.

Implementações de software

Como a exponenciação modular é uma operação importante na ciência da computação e existem algoritmos eficientes (veja acima) que são muito mais rápidos do que simplesmente exponenciar e, em seguida, tomar o restante, muitas linguagens de programação e bibliotecas de inteiros de precisão arbitrária têm uma função dedicada para realizar a exponenciação modular :

• A função embutida do Pythonpow() (exponenciação) [1] leva um terceiro argumento opcional, o módulo
• A BigIntegerclasse do .NET Framework tem um ModPow()método para realizar exponenciação modular
• A java.math.BigIntegerclasse Java tem um modPow()método para realizar exponenciação modular
• MATLAB 's powermodfunção de Symbolic Math Toolbox
• Wolfram Language tem a função PowerMod
• O Math::BigIntmódulo de Perl tem um bmodpow()método [2] para realizar exponenciação modular
• Raku tem uma rotina embutida expmod.
• O big.Inttipo de Go contém um Exp()método (exponenciação) [3] cujo terceiro parâmetro, se não nulo, é o módulo
• A biblioteca BC Math do PHP tem uma bcpowmod()função [4] para realizar exponenciação modular
• A biblioteca GNU Multiple Precision Arithmetic Library (GMP) contém uma mpz_powm()função [5] para realizar a exponenciação modular
• Função personalizada @PowerMod()para FileMaker Pro (com exemplo de criptografia RSA de 1024 bits )
• O opensslpacote de Ruby possui o OpenSSL::BN#mod_expmétodo [6] para realizar a exponenciação modular.
• O HP Prime Calculator possui a função CAS.powmod () [7] para realizar a exponenciação modular. Para a ^ b mod c, a não pode ser maior que 1 EE 12. Esta é a precisão máxima da maioria das calculadoras HP, incluindo o Prime.

Veja também

• Redução de Montgomery , para calcular o resto quando o módulo é muito grande.
• Multiplicação de Kochanski , método serializável para calcular o restante quando o módulo é muito grande
• Redução de Barrett , algoritmo para calcular o resto quando o módulo é muito grande.

Referências

links externos

• Schneier, Bruce (1996). Criptografia aplicada: protocolos, algoritmos e código-fonte em C, segunda edição (2ª ed.). Wiley. ISBN 978-0-471-11709-4.
• Paul Garrett, applet Java de exponenciação modular rápida
• Gordon, Daniel M. (1998). "A Survey of Fast Exponentiation Methods" (PDF) . Journal of Algorithms . Elsevier BV. 27 (1): 129–146. doi : 10.1006 / jagm.1997.0913 . ISSN  0196-6774 .