|
|
Modular Arithmetic
RSA cryptography (named for its inventors Rivest, Shamir, and Adelman) exploits properties and interrelations of humongous numbers, constructed as large powers of huge numbers. Through a neat mathematical trick called modular arithmetic, the
computer avoids working with the humongous numbers themselves. Let's first learn about modular arithmetic before tackling RSA itself.
The number X (mod Y) is the remainder when X is divided by Y. (Remember X (mod Y) is pronounced X modulo Y.)
| For example: |
7 modulo 3 is 1 |
| |
|
| because: |
7 = 2 * 3 + 1 |
That is, when you divide 7 by 3, you get a remander of 1.
The "modulo Y" terminology can also be used in the following way:
Z = X (mod Y), meaning that Z and X have the same remainder when divided by Y.
| For example: |
7 = 25 (mod 3) |
| |
|
| because: |
7 = 2 * 3 + 1
25 = 8 * 3 + 1 |
|
ToC | Next
|
Last Modified: August 2008
|
|