Posts

Introduction The next topic we will cover in mathematics foundations is the Extended Euclidean Algorithm (EEA) and modular inverse. In the topic Introduction to Modular Arithmetic we discussed that division is tricky in modular arithmetic. Today we are going to tackle this problem and see how division works and when we can use it. But first, we need to talk about greatest common divisor and the Euclidean Algorithm. So let’s take this step-by-step. ...

Introduction The best way to introduce the concept of modular arithmetic is with the clock analogy. We know a day has 24 hours (on Earth!). If now is 10:00 and someone says “Let’s meet in 30 hours” you don’t write down “Meeting at 40:00”, you would write down “Meeting at 16:00”. You just performed a modular arithmetic calculation! The easiest way I found to understand the concept of modular arithmetic was associating it with cycles. Anything we count in cycles (hours, days, weeks, and so on) is done using modular arithmetic! Modular arithmetic is used in many different cryptosystems, including modern ones still in use! We will move now to the formal definition that forms the basis of modular arithmetic. ...