Ponieważ operacja na module całkowitym jest homomorfizmem pierścieniowym ( Wikipedia ) od ℤ -> ℤ / nℤ,
(X * Y) mod N = (X mod N) * (Y mod N) mod N
Możesz to zweryfikować samodzielnie za pomocą prostej algebry. (Zauważ, że finał modpo prawej stronie pojawia się ze względu na definicję mnożenia w pierścieniu modułowym.)
Komputery używają tej sztuczki do obliczania wykładniczych w pierścieniach modułowych bez konieczności obliczania dużej liczby cyfr.
/ 1 I = 0,
|
(X ^ I) mod N = <(X * (X ^ (I-1) mod N)) mod NI nieparzysty,
|
\ (X ^ (I / 2) mod N) ^ 2 mod NI parzysty i I / = 0.
W formie algorytmicznej
-- 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
Możesz użyć tego do obliczeń (855^2753) mod 3233tylko z rejestrami 16-bitowymi, jeśli chcesz.
Jednak wartości X i N w RSA są znacznie większe, zbyt duże, aby zmieścić się w rejestrze. Moduł ma zazwyczaj 1024-4096 bitów! Możesz więc poprosić komputer o pomnożenie „na długą” drogę, w ten sam sposób, w jaki wykonujemy pomnożenie ręcznie. Tylko zamiast używać cyfr 0-9, komputer użyje słowa „0-2” 16 -1 lub coś podobnego. (Używanie tylko 16 bitów oznacza, że możemy pomnożyć dwie 16-bitowe liczby i uzyskać pełny wynik 32-bitowy bez uciekania się do języka asemblera. W języku asemblera zazwyczaj bardzo łatwo jest uzyskać pełny wynik 64-bitowy lub w przypadku komputera 64-bitowego , pełny wynik 128-bitowy).
-- 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
To pomnoży X przez Y w czasie w przybliżeniu równym liczbie słów w X pomnożonej przez liczbę słów w Y. Nazywa się to czasem O (N 2 ). Jeśli spojrzysz na powyższy algorytm i go rozdzielisz, będzie to to samo „długie mnożenie”, którego uczą w szkole. Nie masz zapamiętanych tabel czasów do 10 cyfr, ale nadal możesz pomnożyć 1 926 348 x 8 192 004, jeśli usiądziesz i wypracujesz.
Długie mnożenie:
1,234
x 5,678
---------
9,872
86,38
740,4
6,170
---------
7,006,652
W rzeczywistości istnieje kilka szybszych algorytmów do mnożenia ( Wikipedia ), takich jak szybka metoda Fouriera Strassena, a także niektóre prostsze metody, które dodają i odejmują, ale mniej mnożą, a więc ogólnie szybciej. Biblioteki numeryczne, takie jak GMP, są w stanie wybierać różne algorytmy na podstawie tego, jak duże są liczby: transformata Fouriera jest najszybsza tylko dla największych liczb, mniejsze liczby używają prostszych algorytmów.
jest tak duży, jak na maszynę 64-bitową / 32-bitową, nie sądzę, aby mogła utrzymać tak dużą wartość w jednym rejestrze. Jak komputer robi to bez przepełnienia?