From Peasant Arithmetic to Modern Cryptography: The Hidden Magic of Halving and Doubling

As educators, one of our greatest challenges is humanizing mathematics. We often present mathematical operations as sterile, modern inventions delivered from on high, stripping away the messy, brilliant, human history behind them.

Take multiplication, for example. Most of us learned the standard algorithm—stack the numbers, multiply the digits, carry the tens, add it all up. But what if there was a completely different way to multiply? A way that requires no memorization of times tables beyond multiplying and dividing by two?

Enter the Russian Peasant Algorithm. It is a brilliant piece of historical arithmetic that seems like a parlor trick at first glance. But pull back the curtain, and you will find it is the exact same mathematical engine driving the encryption of your modern web browser.

Let's break down how this centuries-old method builds a bridge straight into abstract algebra and computer science.

The Algorithm: Halving and Doubling

The rules of Russian Peasant Multiplication are remarkably simple. Let's say we want to multiply 57 by 623.

1. Create two columns. Write 57 on the left and 623 on the right.

2. In the left column, continually halve the number (ignoring any remainders/decimals) until you reach 1.

3. In the right column, continually double the number to match the rows on the left.

4. Finally, look at the left column. If a number is EVEN, cross out that entire row. If a number is ODD, keep it.

5. Add up all the "kept" numbers in the right column.

Let's run the numbers:

Left (Halve)	Right (Double)	Action	Keep
57	623	57 is odd -> Keep	623
28	1246	28 is even -> Ignore	-
14	2492	14 is even -> Ignore	-
7	4984	7 is odd -> Keep	4984
3	9968	3 is odd -> Keep	9968
1	19936	1 is odd -> Keep	19936

Now, sum the kept values on the right:

623 + 4984 + 9968 + 19936 = 35511.

Check it with a calculator. 57 x 623 is exactly 35511.

Why It Works: Binary in Disguise

Why does this seemingly random process of crossing out numbers work? Because this algorithm is a mechanical, analog way of converting a number into binary (base-2) and applying the distributive property.

When you repeatedly halve the number on the left and note whether it is odd or even, you are actually finding the powers of 2 that make up that number.

• Odd means there is a remainder of 1 (a "1" in binary).

• Even means there is a remainder of 0 (a "0" in binary).

Looking at our left column for 57:

• 57 is odd -> includes 2^0 (which is 1)

• 28 is even -> skips 2^1 (which is 2)

• 14 is even -> skips 2^2 (which is 4)

• 7 is odd -> includes 2^3 (which is 8)

• 3 is odd -> includes 2^4 (which is 16)

• 1 is odd -> includes 2^5 (which is 32)

So, 57 is really just (1 + 8 + 16 + 32).

Because of the distributive property, we can rewrite our original problem:

57 x 623 = (1 + 8 + 16 + 32) x 623

Which expands to:

57 x 623 = (1 x 623) + (8 x 623) + (16 x 623) + (32 x 623)

Notice how the numbers 2 and 4 are completely missing. Because 57 does not contain a 2 or a 4 in its binary expansion, we crossed out the partial products for 623 x 2 and 623 x 4! The Russian peasants were doing binary multiplication centuries before the first computer was plugged in.

Taking It Further: The Engine of Abstract Algebra

Taking this algorithm out of basic arithmetic and dropping it into abstract algebra is where it transforms into a cornerstone of modern computational mathematics. We stop looking at it as multiplying two integers, and instead view the first column as an integer scalar, and the second column as an element in an arbitrary algebraic structure.

1. Group Theory: The "Double-and-Add" Algorithm

In an additive group, if we want to compute the scalar multiplication n * g, the naive approach is g + g + g... done n times.

The Russian Peasant algorithm reduces this from linear time to logarithmic time. "Halving" breaks down the scalar n. "Doubling" means computing g + g = 2g, then 2g + 2g = 4g. "Adding" means accumulating the elements where n is odd.

This exact logic is the engine behind Elliptic Curve Cryptography (ECC). In ECC, 'g' is a point on an elliptic curve. The Double-and-Add algorithm is the only computationally feasible way to multiply a curve point by a massive 256-bit cryptographic private key.

2. Rings and Fields: "Square-and-Multiply"

If we shift from an additive structure to a multiplicative one—like computing x^n in a finite field—the algorithm flips perfectly from addition to multiplication.

• "Halving" remains the binary decomposition of the exponent n.

• "Doubling" the second column becomes squaring: x -> x^2 -> x^4 -> x^8.

• "Adding" the kept values becomes multiplying them together.

To compute x^57, the algorithm gives us:

x^57 = x^32 * x^16 * x^8 * x^1

This is essential for RSA encryption and primality testing, where computing a^(p-1) mod p must be done with gigantic primes without overflowing memory.

3. Polynomial Rings over GF(2)

Consider the polynomial ring GF(2)[x], where coefficients are strictly 0 or 1, and addition is equivalent to the logical XOR operation.

If we multiply two polynomials A(x) and B(x):

• Halving A(x) is a bitwise right-shift.

• Checking odd/even is checking if it has a +1 constant term.

• Doubling B(x) is a bitwise left-shift.

• Adding the kept shifted versions of B(x) is done using XOR.

This process is known as Carry-less Multiplication. It is natively built into modern processors (via the CLMUL instruction set) because it is the exact math required to compute AES encryption.

Conclusion

The beauty of the Russian Peasant algorithm isn't just that it works; it's that it reveals the underlying architecture of mathematics. It shows our students that math isn't a series of disconnected rules, but a continuous thread stretching from fields in ancient Eurasia straight into the silicon of their smartphones. By exploring these connections, we don't just teach calculation—we humanize the subject and invite students to see the wonder within the algorithms.

Unlocking the Matrix: A Guide to Solving Systems of 3 Equations

 

 

If you have ever felt like algebra is just moving letters around a page until a number falls out, solving systems of equations in three variables might seem like the ultimate boss battle. Instead of just dealing with x and y on a flat piece of paper, a third variable (like z, or in our case r, s, and t) brings the math into three-dimensional space. Every equation represents a flat plane, and solving the system means finding the exact 3D coordinate where all three planes intersect.

But before we dive into a full 3x3 system, let's talk about what happens when the number of equations doesn't perfectly match the number of variables.

The Goldilocks Problem: Too Many or Not Enough Equations?

For a system to have a single, beautifully neat solution, you generally need exactly as many equations as you have variables. But what if the balance is off?

• Not Enough Equations (Underdetermined Systems): Let's say you have 3 variables but only 2 equations. This is like having two planes intersecting in 3D space. Instead of meeting at a single point, they meet along an entire line. Because that line stretches on forever, you have an infinite number of solutions. You simply don't have enough restrictions to pin down one specific answer.

• Too Many Equations (Overdetermined Systems): What if you have 3 variables but 4 equations? This is like throwing a fourth plane into the mix. For a single solution to exist, that fourth plane must magically intersect the exact same point as the other three. Usually, this doesn't happen, resulting in no solution (an inconsistent system) unless one of the equations is just a redundant copy or combination of the others.

In Practice: Solving a 3x3 System

Let's look at a practical example. We can walk through a demonstration I did on YouTube

 

In the video, we are given the following system of equations:

1. -4r - s + 3t = 9 - s

2. 3r + 2s - t = 3 - s

3. r + 3s - 5t = 29

Here is the step-by-step breakdown of how to tackle this using the elimination method:

1. Pair Up and Eliminate

The goal is to shrink this 3x3 system into a more manageable 2x2 system by eliminating one variable entirely. The instructor decides to group the top two equations together, and the bottom two equations together. He targets the variable r for elimination.

2. Scale the Equations

To eliminate r from the first two equations, they need opposite coefficients. By multiplying the top equation by 3 and the middle equation by 4, the r terms become -12r and 12r. Adding these new equations together eliminates r and, after combining the lingering s variables, leaves a new two-variable equation: 12s + 5t = 39.

He repeats this process for the second and third equations. By multiplying the third equation by -3 and adding it to the middle equation, r is eliminated again, yielding a second two-variable equation: -6s + 14t = -84.

3. Solve the New 2x2 System

Now, we just have 12s + 5t = 39 and -6s + 14t = -84. By multiplying the second equation by 2, the s terms become -12s, which perfectly cancels out the positive 12s when added together. This leaves an equation entirely in terms of t, which solves to t = -43/11.

4. The Domino Effect (Substitution)

Once you have the first domino (t), the rest fall easily. You plug t back into one of your 2-variable equations to find s. Finally, take both s and t and plug them back into any of the original three equations to solve for your last unknown, r.

Tips and Tricks for Saving Time

If you want to solve these quickly without tearing your hair out, keep these tips in mind:

• Simplify First: In the video example, there were s variables hanging out on both the left and right sides of the equals sign. While the instructor waited to combine them later, a massive time-saver is to combine all like terms and move all variables to one side before you do any multiplication or elimination.

• Target the Easy Variable: Always scan your equations for a variable that has a coefficient of 1 or -1 (like the r in the third equation or the s in the first). It is infinitely easier to multiply a 1 to match another number than it is to find a common multiple for numbers like 7 and 5.

• Keep Your Columns Neat: Write your r's over your r's, and your t's over your t's. A single dropped negative sign or misaligned column will ruin the entire calculation.

The Mental Benefits of the Math Grind

Why do we force students to solve these? Beyond passing a test, solving 3x3 systems provides an incredible workout for your brain's executive functioning:

• Working Memory Expansion: You are forced to hold multiple moving parts in your head at once—remembering which equation you are substituting into while tracking negative signs.

• Rigor and Attention to Detail: These problems are unforgiving. A tiny mistake in step one compounds by step five. Practicing this builds a habit of double-checking work and maintaining intense, hyper-focused attention.

• Cognitive Stamina: In an era of 15-second short-form videos, sitting down to execute a 10-minute, multi-step logical process trains patience and resilience. You learn not to panic when the answer isn't immediately obvious, which is a wildly valuable skill in both academics and life!