Super User is a question and answer site for computer enthusiasts and power users. It only takes a minute to sign up.
Sign up to join this community
Studying some RSA encrypt/decrypt methods, I found this article: An Example of the RSA Algorithm
It requires this to decrpyt this message 
The total result of 
is so big, for a 64-bit/32-bit machine, I don't believe it can hold such a big value in one register. How does the computer do it without an overflow?
This question was a Super User Question of the Week.
Read the blog entry for more details or contribute to the blog yourself
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.
Long multiplication:
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.
mod N at the end of the Chinese Remainder Theorem. ((16 mod 5) is not equal to (4 mod 5) * (4 mod 5): the former is 1, the latter is 16.)
mod is superfluous.
Jul 23, 2012 at 20:20
(X * Y) mod N = (X mod N) * (Y mod N) mod N is true, but it doesn't have anything to do with the Chinese Remainder Theorem.
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!
Further Reading: This article and this one may come in handy for more information.
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).
