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 multiplicative inverse (often written with a -1 exponent, like x-1). By definition, the multiplicative inverse of a number is the value that, when multiplied by the original number inside a specific modulus, gives us the multiplicative identity, which is 1.

There's just one catch: not every number has a multiplicative inverse!

The Golden Rule: Being "Coprime"

For a number to have an inverse in a given modular system, it has to meet one strict condition: the number and the modulus need to be coprime (also called relatively prime). This means they can't share any prime factors. In mathematical terms, their Greatest Common Divisor (GCD) has to be exactly 1.

If the GCD isn't 1, the multiplicative inverse simply doesn't exist, and the operation fails. In cryptography, quickly figuring out whether two massive numbers (hundreds of digits long) are coprime is basically a matter of life or death for the algorithm.

Euclid's Algorithm: A Legacy Thousands of Years Old

To find out if two numbers are coprime, we need their GCD. Luckily, one of the most efficient ways to get it is also one of the oldest methods ever discovered: Euclid's Algorithm.

Instead of breaking huge numbers down into prime factors (something that would take modern computers thousands of years), Euclid's algorithm relies on a clever, lightning-fast trick based on remainders:

  • Take two numbers, x and y.
  • The Greatest Common Divisor of x and y is exactly the same as the Greatest Common Divisor of y and the remainder of dividing x by y (let's call it r).
  • As a formula: GCD(x, y) = GCD(y, r).

By repeatedly swapping the larger number with the remainder, the problem shrinks at an incredible pace, until the remainder finally hits zero. The last non-zero remainder we get is our GCD!

Why Does This Matter So Much?

It's pretty amazing to think that the security protocols protecting our credit cards and emails online today trace back to calculations first worked out in ancient Greece. Those early mathematicians didn't have computers, so they had to come up with incredibly smart ways to do things by hand. And it's that same hand-calculation efficiency that makes their algorithms so perfectly suited to run on today's machines.

To sum up: today we learned that to "divide" we need multiplicative inverses, that these only exist when the GCD is 1, and that Euclid's Algorithm lets us check this condition in a fraction of a second. In the next lesson, we'll take the final step: we'll adapt this ancient algorithm (into the Extended Euclidean Algorithm) so that instead of just telling us whether the inverse exists, it actually calculates it for us. Stay tuned!

References and Study Material

  • Coursera: Mathematical Foundations of Cryptography (Lesson 3: Multiplicative Inverses and Euclid's Algorithm).
  • Daniele Venturi (2012). Crittografia nel Paese delle Meraviglie. Springer. (Introductory chapters on modular algebra).
  • Carlo Casolo. Appunti di Teoria Elementare dei Numeri. University of Florence. (For the full proofs behind the Euclidean algorithm).

Comments

Post a Comment

Popular posts from this blog

How to Install Ubuntu 24.04 WSL on Windows 10 and 11

-
Introduction This guide shows you step-by-step how to install Ubuntu 24.04 LTS using WSL (Windows Subsystem for Linux) on Windows 10 or Windows 11. It's a great solution to run Linux without dual boot or virtual machines. Requirements Windows 10 (version 2004 or later) or Windows 11 Internet connection Administrator access 1. Enable WSL Open PowerShell as administrator and run this command: wsl --install This command enables the necessary features, installs the WSL platform, and downloads Ubuntu (usually the latest stable version). 2. Install Ubuntu 24.04 Manually (if needed) If you want to install Ubuntu 24.04 specifically, you can do it manually: wsl --install -d Ubuntu-24.04 Or if WSL is already installed: wsl --list --online wsl --install -d Ubuntu-24.04 3. First Launch and Setup After installation, open Ubuntu from the Start Menu. The first time you launch it, y...
Read more

Introduction to Rust: Writing Your First "Hello, World!"

-
Getting Started with Rust: A Beginner’s Guide Getting Started with Rust: A Beginner’s Guide Published on July 20, 2025 Setting Up the Workspace First, we need to establish a directory to store our code. While Rust is indifferent to its location, it is good practice to keep your projects well-organized. Open a terminal (or command prompt) and create a directory for your project. For Linux, macOS, and PowerShell (on Windows): # Create a "projects" directory in your home directory mkdir ~/projects # Enter the newly created directory cd ~/projects # Create the directory for our specific project mkdir hello_world # Enter the project directory cd hello_world For the Windows Command Prompt (CMD): > mkdir "%USERPROFILE%\projects" > cd /d "%USERPROFILE%\projects" > mkdir hello_world > cd hello_world Writing and Executing the P...
Read more

Getting Started with Cargo in Rust: A Beginner-Friendly Guide

-
Getting Started with Cargo in Rust: A Beginner-Friendly Guide Cargo is the default build tool and package manager for Rust. It helps you build your code, download libraries (called dependencies ), and keep everything organized. 1. What Is Cargo? When you use Cargo, you don’t have to compile your code manually with rustc . Cargo makes everything easier, especially for bigger projects. You can: Build your code Add external libraries (dependencies) Run your program Check for compile-time errors 2. Check if Cargo is Installed If you installed Rust using the official method ( rustup ), Cargo is already installed. To check, run this command in your terminal: $ cargo --version If you see a version number, you're ready! 3. Create a New Project Now, let’s create a new Rust project using Cargo: $ cargo new hello_cargo $ cd hello_cargo This creates a folder named hello_cargo with two important things inside: Car...
Read more