Como os computadores podem calcular a matemática exponencial sem erros de estouro?

Estudando alguns métodos de criptografia / descriptografia de RSA, encontrei este artigo: Um Exemplo do Algoritmo RSA

Requer que isso descriptografe esta mensagem

O resultado total de é tão grande, para uma máquina de 64 bits / 32 bits, não acredito que possa conter um valor tão grande em um registro. Como o computador faz isso sem transbordar?

Esta pergunta foi uma pergunta da semana para superusuários .
Leia a entrada do blog para obter mais detalhes ou contribua com o blog você mesmo

Como a operação do módulo inteiro é um homomorfismo em anel ( Wikipedia ) de ℤ -> ℤ / nℤ,

(X * Y) mod N = (X mod N) * (Y mod N) mod N

Você pode verificar isso sozinho com um pouco de álgebra simples. (Observe que a final moddo lado direito aparece devido à definição de multiplicação em um anel modular.)

Os computadores usam esse truque para calcular exponenciais em anéis modulares sem precisar calcular um grande número de dígitos.

               / 1 I = 0,
               |
(X ^ I) mod N = <(X * (X ^ (I-1) mod N)) mod NI ímpar,
               |
               \ (X ^ (I / 2) mod N) ^ 2 mod NI par & I / = 0.

Em forma algorítmica,

-- compute X^I mod N
function expmod(X, I, N)
    if I is zero
        return 1
    elif I is odd
        return (expmod(X, I-1, N) * X) mod N
    else
        Y <- expmod(X, I/2, N)
        return (Y*Y) mod N
    end if
end function

Você pode usar isso para calcular (855^2753) mod 3233apenas registros de 16 bits, se desejar.

No entanto, os valores de X e N no RSA são muito maiores, grandes demais para caber em um registro. Um módulo normalmente tem 1024-4096 bits de comprimento! Assim, você pode ter um computador para fazer a multiplicação da maneira "longa", da mesma forma que fazemos a multiplicação manualmente. Somente em vez de usar os dígitos 0-9, o computador usará "palavras" 0-2 ¹⁶ -1 ou algo parecido. (Usar apenas 16 bits significa que podemos multiplicar dois números de 16 bits e obter o resultado completo de 32 bits sem recorrer à linguagem assembly. Na linguagem assembly, geralmente é muito fácil obter o resultado completo de 64 bits ou para um computador de 64 bits , o resultado completo de 128 bits.)

-- Multiply two bigints by each other
function mul(uint16 X[N], uint16 Y[N]):
    Z <- new array uint16[N*2]
    for I in 1..N
        -- C is the "carry"
        C <- 0
        -- Add Y[1..N] * X[I] to Z
        for J in 1..N
            T <- X[I] * Y[J] + C + Z[I + J - 1]
            Z[I + J - 1] <- T & 0xffff
            C <- T >> 16
        end
        -- Keep adding the "carry"
        for J in (I+N)..(N*2)
            T <- C + Z[J]
            Z[J] <- T & 0xffff
            C <- T >> 16
        end
    end
    return Z
end
-- footnote: I wrote this off the top of my head
-- so, who knows what kind of errors it might have

Isso multiplicará X por Y em uma quantidade de tempo aproximadamente igual ao número de palavras em X multiplicado pelo número de palavras em Y. Isso é chamado de tempo O (N ² ). Se você olhar para o algoritmo acima e separá-lo, é a mesma "multiplicação longa" que eles ensinam na escola. Você não possui tabelas de tempos memorizadas com 10 dígitos, mas ainda pode multiplicar 1.926.348 x 8.192.004 se sentar e trabalhar com isso.

Multiplicação longa:

    1,234
  x 5,678
---------
    9,872
   86,38
  740,4
6,170
---------
7,006,652

Na verdade, existem alguns algoritmos mais rápidos para multiplicar ( Wikipedia ), como o método rápido Fourier de Strassen, e alguns métodos mais simples que fazem adição e subtração extras, mas menos multiplicação, e acabam sendo mais rápidos no geral. Bibliotecas numéricas como o GMP são capazes de selecionar diferentes algoritmos com base no tamanho dos números: a transformação de Fourier é apenas a mais rápida para os números maiores, números menores usam algoritmos mais simples.

A resposta simples é que eles não podem, por si próprios. De fato, se você adota o conceito de uma máquina de bits x, existe um número limitado de números que pode ser representado por um número limitado de bits, assim como há um número limitado de números que pode ser representado por 2 dígitos em o sistema decimal.

Dito isto, a representação computacional de números muito grandes é um grande componente do campo da criptografia. Há muitas maneiras de representar números muito grandes em um computador, cada um variando conforme o próximo.

Cada um desses métodos tem vantagens e desvantagens diferentes e, embora eu não consiga / não consiga listar todos os métodos aqui, apresentarei um método muito simples.

Suponha que um número inteiro possa reter apenas valores de 0 a 99. Como alguém poderia representar o número 100? Isso pode parecer impossível no começo, mas isso é porque consideramos apenas uma única variável. Se eu tivesse um inteiro chamado unitse um chamado hundreds, eu poderia facilmente representar 100: hundreds = 1; units = 0;. Eu poderia facilmente representar um número maior, como 9223: hundreds = 92; units = 23.

Embora este seja um método fácil, pode-se argumentar que é muito ineficiente. Como a maioria dos algoritmos que ultrapassam os limites do que um computador pode fazer, geralmente é um conflito entre poder (representa um grande número) e eficiência (recuperação / armazenamento rápido). Como eu disse anteriormente, existem muitas maneiras de representar grandes números em computadores; basta encontrar um método e experimentar com ele!

Eu espero que isto responda sua pergunta!

Leitura adicional:Este artigo e este podem ser úteis para obter mais informações.

A maneira como isso pode ser feito (existem maneiras muito mais rápidas de envolver repetidos quadrados e similares) é multiplicando-se e, após cada multiplicação, faça o módulo. Desde que o módulo ao quadrado seja menor que 2 ^ 32 (ou 2 ^ 64), isso nunca terá um estouro.

Da mesma maneira que você pode.

Vou adivinhar que você não sabe de imediato o que é 342 * 189. Mas você conhece os seguintes fatos:

9 * 2 = 18
9 * 4 = 36
9 * 3 = 27
8 * 2 = 16
8 * 4 = 32
8 * 3 = 24
1 * 2 = 2
1 * 4 = 4
1 * 3 = 3

18 + 360 + 2700 + 160 + 3200 + 24000 + 200 + 4000 + 30000 = 64638

Ao conhecer esses fatos simples e ter aprendido uma técnica para manipulá-los, você pode fazer uma aritmética que de outra forma não conseguiria.

Da mesma forma, um computador que não pode lidar com mais de 64 bits de matemática por vez pode facilmente dividir problemas maiores em pedaços menores, executá-los e juntá-los novamente para formar a resposta para o maior, anteriormente problema sem resposta.

No que diz respeito à adição e subtração, muitas CPUs têm um "bit de transporte" que é definido se a operação aritmética exceder. Portanto, se um resultado exigir 8 bytes para armazenar e a CPU tiver 32 bits (o que equivale a 4 bytes de 8 bits), ele poderá realizar duas operações de adição, primeiro na "palavra baixa" e depois na "palavra alta" com o bit de transporte cuidando do estouro. Necessário limpar o bit de transporte primeiro. Essa é uma das razões pelas quais CPUs de bit mais alto aumentam o desempenho, porque isso não precisa ser feito tanto.

Claro que isso é da minha experiência limitada de montador com CPUs de 8 bits. Não sei como o bit de transporte funciona com CPUs modernas com instruções de multiplicação e divisão. As CPUs RISC que não são da Intel também podem se comportar de maneira diferente.

Não sei muito sobre matemática de ponto flutuante, mas basicamente os bytes representam um número fixo de locais, mas não locais específicos. É por isso que é chamado ponto "flutuante". Portanto, por exemplo, o número 34459234 consumiria aproximadamente o mesmo espaço de memória que 3,4459234 ou 3,4459234E + 20 (ou seja, 3,4459234 x 10 ^ 20).