Crypto: How to do division in modular arithmetic

The goal of this post is to explain straightforwardly how to perform division in modular arithmetic in such a way that you actually understand it.

This is a continuation of a series exploring the mathematical foundations of cryptocurrency. Previously:

• Visual GCD Algorithm
• What is a keypair?

There’s plenty of other material out there that covers every base logically and rigorliciously. I’m not doing that here, mostly because I don’t want to. Gordan Savin’s book is probably the best source for this basic number theory stuff.

Motivation

The local motivation is that in "What is a keypair" I wrote down a bunch of formulas that involve division and also said computers suck at dealing with division. So the trick is to do division in modular arithmetic, but I want to tell you how.

But the more important reasons are more general, and understanding them gives you a better taste of what math even is. With that in mind, the following things are true:

• Algebraic geometry (one of the few math terms that means exactly what it sounds like it means), at a fundamental level, largely depends on our ability to divide space.

  Just at a very basic example, if I have points P = {3, 7} and Q = {18, 12}, I can compute a [vector] Q - P = {18-3, 12-7} = {15, 5}, which is the difference between the two points. The way to remember the Q - P directionality convention is P + (Q - P) = Q.

  I can also take the components of that vector and divide them by 5 to describe "one fifth" of the difference between P and Q:

  (1/5) * (Q - P) = {3, 1}

  

  Diagram of P, Q, Q-P, (1/5) * (Q-P)

• The logic that underpins all of the geometry (at least the geometry that we apply in cryptography) is contained entirely within the symbolic language of algebra and numbers.

  The fact that this logic maps to your visual intuitions about space is important, but also, in some more important way, incidental. As you get more advanced in math (especially in geometry), you gradually need to wean yourself off of your reliance on your evolutionary intuitions about space.

  For example, in normal planar geometry, it’s possible to have regular N-gons for any N >= 3: equilateral triangles, squares, regular pentagons, etc. But there’s no regular digons or regular monogons. It’s not possible to make a polygon with 2 sides or 1 side.

  But on the surface of a sphere, that’s entirely possible. A regular monogon is just a great circle. A regular digon can be found by intersecting two different great circles.

  

  The equator is a monogon, which is the boundary of a hemisphere; down the line, it will be important to maintain a strong terminological distinction between the interior of a shape and its boundary.

  It’s not so much that your intuitions are wrong (although that can happen), it’s more that they’re limited. Geometry over time became algebrized not because pure geometric constructions are wrong, but rather because algebra is simply a much richer framework for expressing, manipulating, and discovering true statements about space.

  The converse of that is that there is a lot of algebraic geometry that does map to visual intuitions, often in counterintuitive and exciting ways, but mathematicians neglect to highlight it. Mathematicians are like brilliant musicians in a timeline where musicians only ever publish sheet music.

  You can’t map everything to your visual intuitions, but the more math you can (correctly) map to your visual intuitions, the better.

So with that in mind, what is important (algebraically) about the number 1/5 is that

• (1 / 5) * 5 = 1; it is the [multiplicative inverse] of 5
• there is exactly one such multiplicative inverse for each number (except 0 – still can’t divide by zero)

• all the normal laws of algebra hold when you extend algebra from integers to fractions:

  (A + B) + C = A + (B + C)
  A + B = B + A
  A * (B + C) = A*B + A*C
  etc

Setup

Our original problem is that in mod-P arithmetic (P is prime), for any number N in the range 1 .. P-1, we wish to find the number OneOverN such that

N * OneOverN = 1 mod P

We also want to make sure there is exactly one such number (at least that it’s unique modulo P).

To achieve this, we’re actually going to zoom out, and "prove" what’s called the [Fundamental Theorem of Arithmetic]:

For any two integers N and K, there exist two integers QN and QK such that QN*N + QK*K = gcd(N, K).

In the specific case where K is prime, then of course its gcd with N will be 1, and so we will have

OneOverN*N + DontCare*P = 1;
ie
OneOverN * N = 1 mod P

Solution

If you’ll recall our GCD algorithm basically works off the following equation:

A = q*B + r
    where
        q = A div B
        r = A rem B

And the observation is, by algebra, that any integer that divides both A and B must also divide r. (If this is twisting your brain, take a glance at the visual gcd post), so we can reduce the problem recursively: gcd(A, B) = gcd(B, A rem B) until we get a remainder of r = 0, at which point B is the gcd.

All we’re going to do here is keep track of the Qs and Rs, and cleverly propagate them upwards.

GitHub Gist Link

%% Full: https://gist.github.com/pharpend/a8c1df19b90c4d718a7184e6358ed7ac
%% I tested it a little but you know maybe double check before using this in
%% prod
-module(egcd).
-export([gcd/2, egcd/2, mod_div/3, mod_inv/2, mod/2]).

%% recall
%% NOTIONAL code
%% always want to return positive GCD because autism
%% logically it doesn't matter
gcd(A, 0) when A < 0 ->
    -1*A;
%% fun fact: "greatest" in GCD actually means greatest with respect to the
%% divisibility graph of the integers! NOT "greatest" with respect to the size
%% of the number. And in the divisibility graph, -X and X are at the same
%% level, because
%% - any integer that divides N also divides -N
%% - any integer that N divides, -N also divides
%%
%% Counterintuitively, 0 is the biggest number in the divisibility graph,
%% because
%% - every integer divides 0
%% - no integer is divisible by 0
%%
%% that's logically why 0 can be a backstop here.
%%
%% really more generally this is a search problem on a directed graph, and we're
%% searching for the "greatest lower bound" of the common subgraph between `A`
%% and `B`. `0` is the universal upper bound, so the greatest lower bound (with
%% respect to the divisibility graph) of the set `{N, 0}` is always `N`
%%
%% anyway in math you should always have your ears perked whenever you hear
%% terms like "greatest", because there's often some implicit context swap going
%% on in the background that is condensing 50 pages of hidden context into some
%% dogwhistle
%%
%% dogwhistle oriented programming
gcd(A, 0) ->
    A;
gcd(A, B) ->
    _Q = A div B,
    R = A rem B,
    %% anything that divides both A and B also divides both B and R
    %% recursive step
    gcd(B, R).


-spec egcd(A, B) -> {GCD, QA, QB}
    when A   :: integer(),
         B   :: integer(),
         GCD :: pos_integer(),
         QA  :: integer(),
         QB  :: integer().

%% NOTIONAL code
%%
%% this is often called the "extended gcd algorithm", hence the name egcd
%%
%% Returns {GCD, QA, QB} with the property that `QA*A + QB*B = GCD`

%% always want to return positive GCD because autism
egcd(A, 0) when A < 0 ->
    %% 1*A + 0*0 = A
    {-1*A, -1, 0};
egcd(A, 0) when A > 0 ->
    %% 1*A + 0*0 = A
    {A, 1, 0};
egcd(A, B) ->
    Q = A div B,
    R = A rem B,
    %% same recursive step
    {GCD, QB, QR} = egcd(B, R),
    GCD = QB*B + QR*R,
    %% algebra
    R = A - Q*B,
    GCD = QB*B + QR*(A - Q*B),
    GCD = QR*A + (QB - QR*Q)*B,
    QA_ = QR,
    QB_ = QB - QR*Q,
    {GCD, QA_, QB_}.


mod_inv(X, P) ->
    {1, OneOverX, _DontCare} = egcd(X, P),
    mod(OneOverX, P).

mod_div(X, Y, P) ->
    mod(X * mod_inv(Y, P), P).

mod(A, B) ->
    R = A rem abs(B),
    case R >= 0 of
        true -> R;
        false -> B + R
    end.