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 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
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 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
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.
1,234 x 5,678 --------- 9,872 86,38 740,4 6,170 --------- 7,006,652
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.
The simply answer is that they can’t, not on their own. Indeed, if you take the concept of an x-bit machine, then there is a limited number of numbers which can be represented by a limited number of bits, just like there is a limited number of numbers which can be represented by 2 digits in the decimal system.
That being said, computer representation of very large numbers is a large component of the field of cryptography. There are many ways of representing very large numbers in a computer, each as varied as the next.
Each of these methods have different advantages and disadvantages, and while I do not / can not list all methods here, I will present a very simply one.
Suppose an integer can only hold values from 0-99. How could one represent the number 100? This may seem impossible at first, but that is because we only consider a single variable. If I had an integer called
units and one called
hundreds, I could easily represent 100:
hundreds = 1; units = 0;. I could easily represent a larger number, like 9223:
hundreds = 92; units = 23.
While this is an easy method, one can argue that it is very inefficient. Like most algorithms which push the boundaries of what a computer can do, it is usually a tug-o-war between power (represent large numbers) and efficiency (fast retrieval/storage). Like I said earlier, there are many ways of representing large numbers in computers; just find a method and experiment with it!
I hope this answered your question!
The way that this can be done (there are much faster ways involving repeated squaring and the like) is by multiplying, and after every multiplication take the modulus. So long as the modulus squared is less than 2^32 (or 2^64) this will never have an overflow.
The same way you can.
I’m going to guess that you don’t know offhand what 342 * 189 is. But you do know the following facts:
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
By knowing these simple facts, and having learned a technique to manipulate them, you can do arithmetic that you otherwise couldn’t.
By the same token, a computer that can’t handle more than 64 bits of math at a time can easily break larger problems up into smaller pieces, do those smaller pieces, and put them back together to form the answer to the larger, previously unanswerable problem.
As far as addition and subtraction are concerned, many CPUs have a “carry bit” that is set if the arithmetic operation has overflowed. So if a result will require 8 bytes to store, and the CPU is 32-bits (which equls 4 8-bit bytes), it can do two addition operations, first on the “low word” and then on the “high word” with the carry bit taking care of the overflow. Necessary to clear the carry bit first. This is one reason why higher bit CPUs increase performance because this does not have to be done as much.
Of course this is from my limited assembler experience with 8-bit CPUs. I don’t know how the carry bit works with modern CPUs with multiply and divde instructions. Non-Intel RISC CPUs may also behave differently.
I don’t know very much about floating point math, but basically the bytes represent a fixed number of places, but not specific places. That’s why it’s called “floating” point. So, for example, the number 34459234 would consume roughly the same memory space as 3.4459234, or 3.4459234E+20 (that’s 3.4459234 x 10 ^ 20).