BTC#: Modular Arithmetic

CryptographyBasicsTitle.png

Series: BTC# – Learning to Program Bitcoin in C#

« Previous: Start at the Very Beginning

Next: Big Numbers Are Big »

Clock Arithmetic

It was a bright cold day in April, and the clocks were striking thirteen.

Clocks striking thirteen signify a world gone mad. The opening line of George Orwell’s 1984 is unsettling because in the familiar world, clocks have circular faces; they go round to twelve and then loop back to one again.

ClocksStrike13.png

In the clock arithmetic we’ve known since before we can remember, 12 + 1 = 1. Similarly, 10 + 4 = 2, 6 + 9 =3, and 12 +12 = 12. It’s not regular addition but neither is it alien. We know how clocks work.

The maths that describes how clocks work is the same maths that underpins cryptography, which, if we’re lucky, will help prevent the dystopia foretold in 1984.

Addition and subtraction in clock arithmetic are the same as addition and subtraction in normal arithmetic except that we limit the answer to fit with in the 1-to-12 range. If an answer falls outside the 1-to-12 range, we add or subtract multiples of twelve until we end up with a value inside the range.

Ten o’clock plus four hours would make 14 o’clock, but we ditch the excess 12. Ten o’clock plus four hours is two o’clock. Ten o’clock plus 16 hours is also two o’clock. We’ve just ditched two lots of 12.

ClockArithmetic.png

Subtraction works in a similar way. Six o’clock minus eight hours would make negative-two o’clock, but that’s not a thing so we add twelve and arrive at ten o’clock.

Modular Arithmetic

If you understand clock arithmetic, you understand modular arithmetic. The only real difference is that there’s no such thing as zero o’clock. Clock hours range from 1 to 12, whereas the results of a “mod 12” operation range from 0 to 11.

(6 + 6) mod 12 = 0.

Think of the result of the modulo operation as the remainder of an integer division. When the numbers divide evenly, the remainder is zero.

ZeroRemainder.png

When the numbers don’t divide nicely we get a remainder.

IntegerRemainder.png

For positive numbers this remainder is the result of the modulo operator we’re looking for.

32 mod 5 = 2

(For a bit more mathematical detail, see Chapter 11 of Bruce Schneier’s Applied Cryptography.)

C#: Remainder vs. Modulus

The first fish hook we come across in translating Programming Bitcoin’s Python into C# is when we try to work out the modulus of a negative number.

The Python example given is this:

>>> print(-27 % 13)
12

If you try the same thing in the C# interactive window, you get:

> -27 % 13
-1

That’s because, in C#, ‘%’ is the remainder operator, not a modulo operator. If both numbers are positive it works as expected, but if the dividend, the number being divided, is negative, the remainder will also be negative.

Because the absolute value of the remainder will always be less that the divisor, the simple fix for this is to add the divisor and take the modulus again.

> (-1 + 13) % 13
12

In the spirit of Don’t Repeat Yourself, I created an extension method to do this:

public static class IntegerExtension
{
    public static int Mod(this int x, int mod) => (x % mod + mod) % mod;
}

(GitHub repo)

Alongside, in the spirit of Test Driven Development, I wrote some tests:

[TestClass]
public class IntegerExtensionTests
{
    #region Mod
    [TestMethod]
    public void Mod_positiveDividendPositiveDivisor()
    {
        Assert.AreEqual(6, 19.Mod(13));
    }

    [TestMethod]
    public void Mod_negativeDividendPositiveDivisor()
    {
        Assert.AreEqual(8, (-5).Mod(13));
    }
    #endregion
}

Note the parentheses around the -5 in the second test. If you leave them out, the function call will happen first, followed by the negation, and you’ll get the wrong answer.

With the modulo operation sorted out we can start creating finite fields.

« Previous: Start at the Very Beginning

Next: Big Numbers Are Big »

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s