Como a operação de módulo inteiro é um homomorfismo de anel ( Wikipedia ) de ℤ - > ℤ / nℤ,
(X * Y) mod N = (X mod N) * (Y mod N) mod N
Você mesmo pode verificar isso com um pouco de álgebra simples. (Observe que o% final mod no 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 computar um grande número de dígitos.
/ 1 I = 0,
|
(X^I) mod N = < (X * (X^(I-1) mod N)) mod N I odd,
|
\ (X^(I/2) mod N)^2 mod N I even & 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 3233 com apenas registros de 16 bits, se quiser.
No entanto, os valores de X e N no RSA são muito maiores, muito grandes para caber em um registrador. Um módulo é tipicamente 1024-4096 bits! Assim, você pode fazer com que um computador faça a multiplicação do modo "longo", da mesma forma que fazemos a multiplicação à mão. Apenas em vez de usar dígitos 0-9, o computador usará "words" 0-2 16 -1 ou algo parecido. (Usando 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 de montagem, geralmente é muito fácil obter o resultado total 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 tempo O (N 2 ). Se você olhar o algoritmo acima e separá-lo, é a mesma "multiplicação longa" que eles ensinam na escola. Você não tem tabelas de tempo memorizadas com 10 dígitos, mas você ainda pode multiplicar 1.926.348 x 8.192.004 se você se sentar e resolver 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 de Fourier rápido de Strassen, e alguns métodos mais simples que fazem adição e subtração extras, mas menos multiplicação, e assim terminam mais rápido no geral. Bibliotecas numéricas como o GMP são capazes de selecionar algoritmos diferentes com base em quão grandes são os números: a transformada de Fourier é apenas a mais rápida para os números maiores, números menores usam algoritmos mais simples.