Modular Exponentiation: How "Square and Multiply" Powers Modern Cryptography

-

Welcome back to izytech.dev! In the previous article, we found out how to simulate division in modular arithmetic using the Multiplicative Inverse and the ancient Euclidean Algorithm. Now that we know how to add, multiply, and "divide" numbers safely, we're facing the biggest obstacle of all: powers.

In modern cryptography, encrypting and decrypting a message means taking a number (the message) and raising it to a massive power (the key) inside a modular world. But how do computers handle numbers that huge without crashing?

The Problem With Giant Numbers

When we're working with small numbers, exponentiation is easy. Calculating 3 to the 5th power (35) in a "modulo 143" world can even be done by hand or with a basic calculator, just by reducing the final result.

But what happens if we need to calculate 12,345 raised to the 6,789th power, still modulo 143? We're talking about a number with tens of thousands of digits! Regular programming languages and calculators simply can't handle it: they'd run out of memory or hit fatal rounding errors. And in cryptography, if even the last digit is wrong, the whole message is lost.

Why Can't We Just Reduce the Exponent?

You might think of a shortcut: reduce both the base and the exponent by the modulus 143 before doing the math. Unfortunately, that doesn't work.

As we mentioned earlier, exponents live in a completely different modular world from the one their base lives in. We can't just apply a plain modulus N to the exponent. (We'll uncover the real rules of this "parallel world" in the next lesson, when we talk about Euler's Totient Function!). So we need an algorithm that solves the problem without touching the exponent.

The Solution: The "Square and Multiply" Algorithm

The trick to keeping a computer's memory from "exploding" is called the Square and Multiply algorithm. Instead of multiplying a number by itself thousands of times, we take advantage of the language computers naturally speak: binary code.

Here are the three clever steps behind this method:

  1. Convert the exponent to binary: Any exponent can be rewritten as a sequence of 0s and 1s. For example, the exponent 69 becomes 1000101 in binary.
  2. Square it: We start from our base number. At each step (for every bit of the exponent), we square the previous result. And here's the trick: right after squaring, we immediately reduce the result using the modulus. That way, the number never grows bigger than the square of our modulus!
  3. Multiply: If the matching bit in the binary exponent is a "1", we multiply the partial result by the base number (and reduce again). If it's a "0", we simply skip the multiplication.

Extreme Efficiency for Everyday Security

So why is this algorithm such a big deal? If we used the "brute force" method to calculate a number raised to the 69th power, we'd need to run 69 multiplications. With the Square and Multiply method, all we need to look at is how many bits make up the number 69. Since it only takes 7 bits, the algorithm needs just 7 steps!

The complexity drops dramatically, going from the size of the number itself down to the size of its bits (in math terms, from O(E) to O(log E)). This huge drop in computational difficulty is exactly what lets the tiny chips in our credit cards or smart cards run military-grade encryption in a fraction of a second, using almost no battery or memory.

To sum up: the Square and Multiply algorithm lets us handle enormous calculations by reducing the intermediate results step by step and using the binary form of the exponent. But one question is still open: which "modular world" does the exponent actually live in, and how do we use that to decrypt messages? We'll cover that in the next chapter with Euler's Theorem. Stay tuned!

References and Study Material

  • Coursera: Mathematical Foundations of Cryptography (Lesson 5: Modular Exponentiation and the Square and Multiply Algorithm).
  • Daniele Venturi (2012). Crittografia nel Paese delle Meraviglie. Springer. (For computational efficiency in cryptography and the Fast Powering Algorithm, FPA).
  • Thomas H. Cormen et al. (2022). Introduction to Algorithms. MIT Press. (For an in-depth analysis of algorithmic complexity and large-number arithmetic).

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