izytech.dev

Welcome back to izytech.dev ! In our previous article , we discovered how to simulate division using the Multiplicative Inverse and the Euclidean Algorithm. However, we left a huge question unanswered about modular exponentiation. We know how to calculate giant powers, but we learned a strange rule: the exponent does not live in the same modular world as the base . If the base lives in a mod N world, where does the exponent live? Today, we are going to explore this "parallel universe" and introduce the mathematical magic trick behind modern encryption: Euler's Totient Theorem . The Totient: A Parallel World To understand exponents in modular arithmetic, we must introduce a new concept called the Totient (often represented by the Greek letter Phi, Φ(N) ). The totient of a positive integer N is simply the count of positive integers that are strictly less than N and are relatively prime to N (meaning they share no common prime factors with N...

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...