Because the integer modulus operation is a ring homomorphism (Wikipedia) from ℤ -> ℤ/nℤ,
(X * Y) mod N = (X mod N) * (Y mod N) mod N
You can verify this yourself with a little bit of simple algebra. (Note that the final
mod on the right-hand side appears due to the definition of multiplication in a modular ring.)
Computers use this trick to calculate exponentials in modular rings without having to compute a large number of digits.
/ 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.
In algorithmic form,
-- compute X^I mod N
function expmod(X, I, N)
if I is zero
elif I is odd
return (expmod(X, I-1, N) * X) mod N
Y <- expmod(X, I/2, N)
return (Y*Y) mod N
You can use this to compute
(855^2753) mod 3233 with only 16-bit registers, if you like.
However, the values of X and N in RSA are much larger, too large to fit in a register. A modulus is typically 1024-4096 bits long! So you can have a computer do the multiplication the "long" way, the same way we do multiplication by hand. Only instead of using digits 0-9, the computer will use "words" 0-216-1 or something like that. (Using only 16 bits means we can multiply two 16 bit numbers and get the full 32 bit result without resorting to assembly language. In assembly language, it is usually very easy to get the full 64 bit result, or for a 64-bit computer, the full 128-bit result.)
-- 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
-- Keep adding the "carry"
for J in (I+N)..(N*2)
T <- C + Z[J]
Z[J] <- T & 0xffff
C <- T >> 16
-- footnote: I wrote this off the top of my head
-- so, who knows what kind of errors it might have
This will multiply X by Y in an amount of time roughly equal to the number of words in X multiplied by the number of words in Y. This is called O(N2) time. If you look at the algorithm above and pick it apart, it's the same "long multiplication" that they teach in school. You don't have times tables memorized out to 10 digits, but you can still multiply 1,926,348 x 8,192,004 if you sit down and work it out.
There are actually some faster algorithms around for multiplying (Wikipedia), such as Strassen's fast Fourier method, and some simpler methods which do extra addition and subtraction but less multiplication, and so end up faster overall. Numerical libraries like GMP are capable of selecting different algorithms based on how big the numbers are: the Fourier transform is only the fastest for the largest numbers, smaller numbers use simpler algorithms.