What is modular arithmetic?

Modular arithmetic is something that we use every day in our lives. It has been around since the invention of time (in a sense). So, what is it?

Every time we look at a clock or try to calculate the time, we use modular arithmetic, which is why it's also called clock arithmetic. So, imagine that you have an appointment in 5 hours, and right now it's 9 a.m. What time is the appointment at? Obviously, it would be at 2 p.m, but what method did you use to figure that out.

Firstly, we do some regular arithmetic. We just do 9+5, which is 14. Now, here comes the modular part. Since we're using a 12-hour clock, we'll use modulo 12 to calculate the time. Simply divide 14 by 12 and take the remainder of 2. That's what we call the modulus. So, if we write it as an equation, we get:

9 + 5 ≡ 2 (mod 12)

If you think about it, modular arithmetic basically shows you the remainder of dividing a normal answer by the modulo. The numbers kind of 'wrap around', so that once you've counted through 12, you get back to the start. However, there's many other modulo that you could use, such as if we do the same calculation using modulo 8, we get:

9 + 5 ≡ 6 (mod 8)

We link the answer to the normal arithmetic to the modular by saying that 14 is congruent (the symbol ≡) to 2 modulo 12 or 14 is congruent to 6 modulo 8.

Now, we get to the applications of it. Of course, there's the clock, but another reason people may not know is cryptography. Ciphers like RSA use modular arithmetic in a very clever way to encode a message. That is using modular arithmetic as a one-way function. I've already talked a bit about how RSA works on a basic level in another article (check it out here), but this article goes a lot deeper into it, as the maths behind it is incredibly smart.

One-way functions are easy to complete, yet difficult to reverse (at least in terms of computing power). It's similar to mixing a batch of paint together. Adding blue and yellow to a can and stirring them to create green is easy, but it is basically impossible to un-mix the paint and return to the original colours.

RSA employs two different one-way functions to make the cipher practically unbreakable currently. The first one used is multiplication and factorisation. RSA works by first establishing 3 numbers, N, p and q. All of these combine to form the private and public keys used in RSA.

p and q are two super-large prime numbers that we multiply together to get N. So, as an equation, N=pq. The way that RSA works is that if you know p and q then you can decipher any message that is encrypted using N. Since N is the public key, everyone in the world has access to it and could therefore factor it to find p and q, so all messages sent using N can be read.

However, this is a lot more difficult than it seems. N can be as large as 10^308, and the only way to find the two factors is by going through every single prime number until you can find one that is a factor of N. This makes it a one-way function as it is easy to multiply 2 very large numbers together, but factoring them takes even longer and there are no shortcuts in doing so.

So, now that we have N, p and q, what do we do. Well, we also have to pick another number, which we will call e. There is one technicality to what the value of e can be. We have to make sure that e is relatively prime to [p-1]X[q-1], a number that we'll use later in this process. Relatively prime may sound confusing, but it just means that there are no common factors of these two numbers apart from 1.

So, if you want people to send you secure messages, you publish N and e as the public key, and then everyone who wants to send you a message uses these to encrypt their message.

Now, we get to the modular part. We can use them to create a one-way function. We do this by firstly taking the message that someone else wants to send to us and converting it to a number using ASCII. This number is what we are enciphering and is what third parties are trying to take from us. We will call this number M. Secondly, we will put this number to the power of e. To complete the encipherment, we will put this number to modulo N. So, if we define C as the encrypted message, the equation would be:

C ≡ M^e (mod N)

How does this act as a one-way function? Well, if we took an unknown number such as x and put it to the power of 3 using modulo 5, we could write the equation:

x^3 (mod 5) ≡ 3

In this case, x=7. Now, if I asked you to find x but there was no modulo, it would be very easy as we could keep on trying different numbers and we could tell if we're getting closer or further away. If x^3=343, we can try numbers like 6, and when we realise the 6^3 is 216, we can tell that we need to increase our value of x as 216 is smaller than 343.

However, let's go back to using a modulo. If we do 216 (mod 5), we get an answer of 1. This literally doesn't help us refine our estimate at all, so we may start going for lower values of x instead to the higher value we actually need to go for. Therefore, this makes it a lot harder. Now, imagine doing this but instead for a giant number that represents an entire message. It would obviously take a lot longer, even with a powerful computer, making it a one-way function.

Once the encryption has happened, the result C is sent to us. Any third parties who want to decipher our message will be unable to do it. However, if they can't, how will we?

For this, we have to calculate a special number called d, the decryption key. To calculate this, we need to use p and q, the private key. There's a complex equation to do this, which is:

e X d ≡ 1 (mod [p-1]X[q-1])

To solve this, we need to go even deeper into mathematics and find something called the modular multiplicative inverse. A normal multiplicative inverse is the number that you multiply another number by to get an answer of 1. For all rational numbers, the multiplicative inverse of it is the reciprocal. For example:

29 X 1/29 = 1

The modular multiplicative inverse of an integer is a number that we can multiply it by so that the remainder of it is 1 when divided by a modulo. So, in the actual calculation for getting d, we're trying to find a value of d that when multiplied by e divides by [p-1]X[q-1] to give a remainder of 1. Simple, right?

To decrypt the message now is simple. We use the equation:

M ≡ C^d (mod N)

And that's it! We have successfully encrypted and decrypted a message using RSA! This probably seems really long but remember that 1) computers are a lot faster than us and 2) the computer literally does everything for you. We don't have to try searching up our friend's public key before we send a message to them, the computer does it for us.

As I've said multiple times, privacy in the digital age is the priority for many people. Information is basically a new currency, and modular arithmetic allows us to keep it safe. There are many other uses of course, but I believe that RSA is the most important one.