Linxz' Blog

Still trying to think of something witty, I will let you know once I get something...

Home Blog Categories
17 February 2019 | 9 minutes to read

Equivalence Classes

Tags: crypto


Now, last post we talked about modulo and if you remember at the end I told you that the fact the remainder is not unique runs much deeper than just a coincidence and as such I’m going to introduce you to what we call equivalence classes. If you have not already, I highly advise you go back & read the last post as if you don’t you might have a hard time understanding what I am talking about here or what this means for us & cryptography.

Equivalence Classes

So as a recap of the last post, you might/should remember that we looked at some basic congruence modulo examples and we came to the conclusion that the remainder is not unique, let’s take a look at another example so that I can introduce to you the idea of a equivalence class.

Remember, we look at how many times the 5 fits into the 12 and as such we can write this as

and we can do our check that we did before by writing $5 \vert (12-2)$ and as I’m sure you’re aware, 5 does divide 10 so that is correct. But remember, we said the remainder is not unique so we could also write this as

and like before we can go into negative numbers if we so wish

and what you should have observed here is that we can define an infinite set here with a gap of 5 between all of the numbers. In other words, the below is an equivalence class for modulo 5. It is important to know that all the elements of this class will behave equivalent modulo 5 and we will now move onto what this actually means.

The observant of you might have noticed I said “an equivalence class for modulo 5” and if you did notice I said that, well done - so what does this mean? Well, it means that there is more than just one equivalence class for modulo 5 and now I’m going to show you all of them.

All Equivalence Classes Modulo 5

As I mentioned, there is more than one equivalence class for modulo 5 and now we’re going to look at what they are and how many there are. Before I tell you, maybe try and guess and tell me how many you think there are, wait… I don’t have Disqus on my posts so that is probably pointless, oh well I’ll just show you.

So, I’ve already shown you one equivalence class for Modulo 5 now let me show you another, this is a very, very basic one and I’m sure that most of you have probably worked it out already but if you haven’t, don’t worry!

Now, off the back of this I have two important questions for you, firstly - how many elements/members are in this class? Your answer should be… Infinite. That’s right, there are infinite elements in this class why you might ask? Well, because I can just add 5 forever and it never stops, 15, 20, 25, 30 or I could go the other way, -15, -20,-25, -30 you see? It has infinite elements! The next big question however, does this class catch all integers? And this time your answer should be… No, it does not. If you’re unsure as to why then let me put it simply, is 7 an element in this class? Again your answer should be no, it does not. So no this equivalence class does not catch all integers but this still is an infinite class!

So now if I asked you, where is the number 6? Your answer should be, well Linxz it must be in a different equivalence class and yes, you’re right it is! So let’s define what that class would look like.

Once again the class is infinite however we’re still not catching all integers for example, we still don’t see 7 and so it must be in a new class which we can define once again.

As you can see we now have 5 equivalence classes for modulo 5, they are all infinite and we’ve now covered all integers in one of these 5 classes, meaning we have caught all integers and any integer will appear somewhere in one of these classes at some point, simple right? But Linxz! You said in cryptography we want to work in Finite sets, you’re right! I did say that which is why when we do the computation in this case we limit ourselves to only 5 elements!

Now, one thing I did not mention earlier but is very important to this idea of equivalence classes is that all members of the class will behave equivalently - you might be thinking “Linxz, what the hell does that mean!?” and if you are, slow down I’m about to show you :)

All Members of a Given Equivalence Class Behave Equally

What does this mean? Well, for a given modulus $ m $ it does not matter which element from a class we choose for computation because all members behave the same, what does this mean for us? Well, it means that if we’re doing computation with a fixed modulus we can choose a class element that will result in the easiest computation, this has major, major practical benefits which we will look at now.

So, it just so happens that the core operation in many public-key cryptosystems is to perform exponentiation in the form $ x^{e} mod m $. We’re going to look at the two ways of computing this with an example, just remember that these numbers are laughable compared to the ones we would use in a real public-key system. The first way I’m going to show you is actually very stupid and it is because of this sentence “all members of a given equivalence class behave equally” that this is a stupid method.

Now, there are two ways of doing this computation, the first way is the dumb way but I’ll show you it first then maybe you will be able to figure out the second way before I finish.

First Way (Stupid Way)

Second Way (Smart Way)

Now, you might be thinking - wait Linxz, now we’re just going back to the stupid way and you’re right! Which is why we don’t continue with this method, and this is where our statement comes in. What we want to do now is replace our 81s with the smallest positive member for modulo 7 which turns out to be 4 because $ 81 = 11 \cdot 7 + 4 $ so it now becomes

If you’re still confused, I’ll explain it in English instead of math notation. So, we first got our 81 again then we reduced 81 by modulo 7 which gave us 4 times 4 which as you know is 16. We then asked, how many times does 7 go into 16? It goes twice with a remainder of 2 and that is it! I want to stress that this is so, so, so important we will see this in RSA, Diffie-Hellman and most public-key cryptosystems, you must understand this principle!

The last thing I want to mention is this, you might be wondering which one do we pick? Earlier I introduced you to all the equivalence classes modulo 5 and they are all correct, so which one do we pick? Well, we try to aim to compute with the smallest positive member of each equivalent class as it is far more convenient.

Closing Notes

Phew! That was a lot of math but, very important to public-key cryptography as we mentioned earlier! In the next post we will look at Integer Rings are on a high-level and then we’ll start covering historic ciphers!

Thank you for reading! See you next time! :D