The Multiplicative Inverse and Euclid's Algorithm: How to "Divide" in Cryptography
Welcome back to izytech.dev ! In the previous article , we looked at the beating heart of cryptography: modular arithmetic. We saw how computers use the math of "remainders" to keep numbers small and calculations fast. But we ended that lesson with a big roadblock: in this circular world, division doesn't exist . So if we can't divide a number to decrypt a message, how do we go back? The answer lies in one of the most fascinating ideas in number theory: the Multiplicative Inverse , along with an algorithm that's thousands of years old and still lets us calculate it today. The Illusion of Division Think about regular math for a second. Dividing a number by 5 is exactly the same as multiplying it by 1/5 (its reciprocal). In cryptography, we use this exact same logic, but since we can't work with decimals or fractions, we need to find a whole number that behaves just like that reciprocal. This special number is called the multiplicativ...