Поскольку операция целочисленного модуля является кольцевым гомоморфизмом (Википедия) из ℤ -> ℤ / nℤ,
(X * Y) mod N = (X mod N) * (Y mod N) mod N
Вы можете убедиться в этом сами с помощью небольшой алгебры. (Обратите внимание, что последний mod
в правой части появляется из-за определения умножения в модульном кольце.)
Компьютеры используют этот трюк для вычисления экспонент в модульных кольцах без необходимости вычисления большого количества цифр.
/ 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.
В алгоритмической форме
-- 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
Вы можете использовать это для вычисления (855^2753) mod 3233
только с 16-битными регистрами, если хотите.
Однако значения X и N в RSA намного больше, слишком велики, чтобы поместиться в регистр. Модуль обычно имеет длину 1024-4096 бит! Таким образом, вы можете заставить компьютер выполнять умножение "длинным" способом, так же, как мы делаем умножение вручную. Только вместо цифр 0-9 компьютер будет использовать "слова" 0-2 16 -1 или что-то в этом роде. (Использование только 16 бит означает, что мы можем умножить два 16-битных числа и получить полный 32-битный результат, не прибегая к языку ассемблера. На ассемблере обычно очень легко получить полный 64-битный результат, или для 64-битного компьютера - полный 128-битный результат.)
-- 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
Это умножит X на Y за время, примерно равное количеству слов в X, умноженному на количество слов в Y. Это называется O(N 2) время. Если вы посмотрите на алгоритм выше и выберете его отдельно, это то же самое "длинное умножение", которому они учат в школе. Таблицы времени не запоминаются до 10 цифр, но вы все равно можете умножить 1 926 348 x 8 192 004, если сядете и решите это.
Длинное умножение:
1,234
x 5,678
---------
9,872
86,38
740,4
6,170
---------
7,006,652
На самом деле есть несколько более быстрых алгоритмов умножения (Википедия), таких как быстрый метод Фурье Штрассена, и некоторые более простые методы, которые делают дополнительное сложение и вычитание, но меньше умножения, и, следовательно, в итоге быстрее в целом. Числовые библиотеки, такие как GMP, способны выбирать различные алгоритмы в зависимости от того, насколько большие числа: преобразование Фурье является самым быстрым для самых больших чисел, меньшие числа используют более простые алгоритмы.