I’m always really surprised, disappointed, and a bit gassy over how despised anything involving even the simplest of Mathematics is by most Computer Scientists; the mere mention of the word “derivative” is enough to invoke a cringe of repressed childhood-pain from all but the strongest-willed of programmers. However, even if a ‘matrix’ is nothing more to you than a bootleg DVD you torrented when you were 16, you can still enjoy the limitless pleasure provided by a basic understanding of modern mathematics. In fact, after a few simple preliminaries in modular arithmatic (don’t worry – it’s not nearly as scary as it sounds), the algorithm for RSA encryption is actually incredibly simple – so buckle your seatbelt and put on your thinking cap for today’s magical adventure into the strange and wondrous world of mathematics.

1. Modular Arithmetic

If you are still reading this, then either you were misdirected here by the malevolent Internet traffik demon (which means my monetary bribes are working), or you sincerely want to learn how RSA encryption works, in which case I hope our almighty five-legged overlord takes mercy on your soul as it burns in the deepest pits of hell.

Most programmers are familiar with the syntax

18 mod 5

In case you are not, mod (which stands for modulus) simply gives back the remainder from dividing the left number by the right. Since the remainder of 18/5 is 3, this means

18 mod 5 = 3

In mathematics, the syntax is a bit different. Rather than saying “the modulus of 18 by 5 is equal to some number (ie. 3)”, we say “18 is congruent to some number mod 5." It is just as correct to say “3 is congruent to 18 mod 5” as it is to say “18 is congruent to 3 mod 5.”

We would write this latter statement as 18 ≡ 3 (mod 5).

What we are really saying using this notation is that if we take left-hand of the equation and mod it by 5, then take the right-hand side and mod *it* by 5, we will get the same thing. When we restrict our world to numbers mod 5 like this, 18 and 3 act like the same number.

This new notation allows us to do some very cool symbol-pushing (all of which, I assure you, is completely valid). For instance, it can be shown that the properties of most normal integer operations – addition, subtraction, multiplication, exponentiation – carry over to modular arithmetic, so that, for example,

x^{a} * x^{b} ≡ x^{(a+b)} (mod n)

It is also rather obvious (and, of course, can be proved) that when adding, subtracting, or multiplying, you can replace one number with another it is congruent to; so, for instance, since 18 ≡ 3 (mod 5),

18^{2} ≡ 3^{2} ≡ 9 ≡ 4 (mod 5)

When working with negative numbers mod n, we find congruencies by simply adding n repeatedly until we get a positive number. For example,

-21 ≡ -1 ≡ 19 (mod 20)

This gives us a new trick to put in our bag for determining (without a calculator) some large numbers mod n:

19^{10} ≡ (-1)^{10} ≡ 1 (mod 20)

Cool!

In modular arithmetic, we are usually concerned with only integers; this means that numbers don’t have fractional inverses the way they do in regular arithmetic. That is, there is no number you can multiply 5 by (mod 10) to get 1, since we’re not considering 1/5 a number. Nonetheless, there are certain cases^{†} in which numbers in modular arithmetic still have inverses! For instance, notice that 7 * 3 ≡ 21 ≡ 1 (mod 10), so 7 and 3 are inverses (mod 10).

For a final example to show just how powerful modular arithmetic is, let’s calculate the last decimal digit of, say, 3^{403}. Notice that “the last decimal digit” is the same as “its value (mod 10).” Hence, we’re looking to reduce

3^{403} (mod 10).

The solution is actually quite simple. First, we realize that

3^{4} ≡ 81 ≡ 1 (mod 10)

Then, since 3^{403} = (3^{4})^{100} * 3^{3},

3^{403} ≡ (3^{4})^{100} * 3^{3} ≡ (1)^{100} * 3^{3} ≡ 27 ≡ 7 (mod 10)

Thus, in less than a minute, we just determined that the last digit of 3^{403} is 7, without a calculator!

^{†}A number has a unique inverse (mod n) if and only if it is

*relatively prime*to n. The concept of “relatively prime” will be briefly discussed in the next post.

## 5 Comments

Part 1!? You mean there’s more of this crap?

fuck you and your math.

dude, language. this site is for all ages to enjoy. do it again and your banned

how do you ban anynomous?? I know you’re god… but even god has his limits. you’re spelling proves this.

Are you having a conversation with yourself?