AlgoScope

Number Theory Basics

Each of these looks like arithmetic, but each is really a short loop over a small list: remainders, candidate divisors, binary digits, clock positions, prime factors. Drawing the list is what makes the cost obvious.

The player

Finding the greatest common divisor of 48 and 18 with Euclid's algorithm.480181

Find the largest number that divides both 48 and 18. Euclid's trick: it also divides 48 mod 18, so keep replacing the pair with (b, a mod b) until the remainder is 0.

How it runs, step by step

  1. Find the largest number that divides both 48 and 18. Euclid's trick: it also divides 48 mod 18, so keep replacing the pair with (b, a mod b) until the remainder is 0.

    Finding the greatest common divisor of 48 and 18 with Euclid's algorithm.

  2. 48 mod 18 = 12. Any divisor of 48 and 18 divides 12 too, so the pair becomes (18, 12).

    48 modulo 18 is 12. The pair is now 18 and 12.

  3. 18 mod 12 = 6. Any divisor of 18 and 12 divides 6 too, so the pair becomes (12, 6).

    18 modulo 12 is 6. The pair is now 12 and 6.

  4. 12 mod 6 = 0. Any divisor of 12 and 6 divides 0 too, so the pair becomes (6, 0).

    12 modulo 6 is 0. The pair is now 6 and 0.

  5. The remainder hit 0, so the last non-zero value, 6, is the answer. gcd(48, 18) = 6 in 3 steps, and the numbers shrank fast: this is O(log n).

    The greatest common divisor of 48 and 18 is 6.

The code

Number Theory Basics, in Python

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

def is_prime(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return True

def pow_mod(base, exp, m):
    result = 1
    b = base % m
    e = exp
    while e > 0:
        if e & 1 == 1:
            result = result * b % m
        b = b * b % m
        e = e >> 1
    return result

def mul_mod(a, b, m):                       # a x b mod m with no product larger than 2m
    result = 0
    x = a % m
    y = b
    while y > 0:
        if y & 1 == 1:
            result = (result + x) % m       # this power of two of b is in the product
        x = (x + x) % m                     # double a, reduced
        y = y >> 1
    return result

Number Theory Basics, in JavaScript

const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));

function isPrime(n) {
  if (n < 2) return false;
  let d = 2;
  while (d * d <= n) {
    if (n % d === 0) return false;
    d++;
  }
  return true;
}

function powMod(base, exp, m) {
  let result = 1;
  let b = base % m;
  let e = exp;
  while (e > 0) {
    if ((e & 1) === 1) result = (result * b) % m;
    b = (b * b) % m;
    e = e >> 1;
  }
  return result;
}

function mulMod(a, b, m) {                         // a x b mod m with no product larger than 2m
  let result = 0;
  let x = a % m;
  let y = b;
  while (y > 0) {
    if ((y & 1) === 1) result = (result + x) % m;  // this power of two of b is in the product
    x = (x + x) % m;                               // double a, reduced
    y = y >> 1;
  }
  return result;
}

Number Theory Basics, in Kotlin

fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)

fun isPrime(n: Int): Boolean {
    if (n < 2) return false
    var d = 2
    while (d * d <= n) { if (n % d == 0) return false; d++ }
    return true
}

fun powMod(base: Int, exp: Int, m: Int): Int {
    var result = 1; var b = base % m; var e = exp
    while (e > 0) {
        if (e and 1 == 1) result = result * b % m
        b = b * b % m
        e = e shr 1
    }
    return result
}

fun mulMod(a: Int, b: Int, m: Int): Int {           // a x b mod m with no product larger than 2m
    var result = 0; var x = a % m; var y = b
    while (y > 0) {
        if (y and 1 == 1) result = (result + x) % m  // this power of two of b is in the product
        x = (x + x) % m                              // double a, reduced
        y = y shr 1
    }
    return result
}

Write it yourself

Define gcd(a, b) and return the greatest common divisor of a and b. It runs in your browser against this lesson's own 2 examples.

// Replace the larger number by its remainder against the smaller, until one of them is zero.function gcd(a, b) { return 0;}
6 linesTab indents. Escape, then Tab, leaves the editor. Ctrl-Enter runs (Cmd-Enter on a Mac).

    Remember

    • Euclid shrinks the pair fast, so gcd is O(log n) rather than trying every divisor.
    • Trial division only needs to go to the square root: any bigger factor pairs with a smaller one.
    • Fast exponentiation costs one squaring per bit of the exponent, not one multiply per unit of it.

    Where this is used

    TLS handshakes and RSACryptography

    Diffie-Hellman and RSA both come down to computing base raised to an exponent, modulo a large m, where the exponent is a 2048-bit number. Square-and-multiply turns that into roughly 2048 squarings and at most 2048 multiplies, which is a few milliseconds, where stepping one multiply at a time would never finish. OpenSSL spends this work in BN_mod_exp, a windowed version of the same loop that handles several exponent bits at a time, with a separate constant-time path for secret exponents so the running time does not reveal which bits were set.

    Python's fractions moduleStandard libraries

    Every Fraction that CPython constructs is divided through by math.gcd of its numerator and denominator before it is stored. Without that step, summing a thousand fractions would leave a denominator equal to the product of all thousand denominators, and the arithmetic would be crawling over numbers thousands of digits long. Euclid keeps the reduction to a handful of steps per operation, which is what makes exact rational arithmetic practical at all.

    Redis Cluster hash slotsDatabases

    Redis Cluster maps every key to one of 16384 slots using CRC16 of the key modulo 16384, and every slot is assigned to one node. Because the slot is pure arithmetic, any client can work out which node holds a key without asking the cluster first. Rebalancing then means handing over slot numbers rather than rehashing every key, since a key's slot never changes when nodes come and go.

    IBAN check digitsPayments

    The ISO 7064 MOD-97-10 scheme sets a bank account number's two check digits so that the whole IBAN, read as one integer of thirty or more digits, leaves a remainder of 1 when divided by 97. No built-in integer type is that wide, so implementations carry a running remainder through the string a few digits at a time, which is the same trick as reducing as you go in mulMod. The modulus is doing real work here: 10 is a primitive root modulo 97, so every digit position carries a different weight and transposing two digits always changes the remainder.

    Why it works this way

    Why does Euclid finish in so few steps?

    For any b at or below a, the remainder a % b is always below a / 2. If b is at most a / 2 then the remainder is smaller than b and so smaller than a / 2. If b is larger than a / 2 then the quotient is 1 and the remainder is a - b, again below a / 2. One step turns (a, b) into (b, a % b), so it takes two steps for that halved value to reach the front of the pair, and the leading number is below half of what it was every two steps. That is what gives O(log n). The slowest possible input is a pair of neighbouring Fibonacci numbers, where every quotient comes out as 1, so each step is a single subtraction and nothing more.

    % is a remainder, not a clock position

    In Kotlin, Java, C and JavaScript the sign of % follows the left operand, so -1 % 12 is -1 and not 11. Any code that treats the result as a position on a ring breaks the first time the input goes negative: a wrapped buffer index, an hour before midnight, a hash that happened to come out negative. Write ((a % m) + m) % m when the value can be negative, or use Math.floorMod in Java and Kotlin's Int.mod. Python's % is already the floored version and returns 11.

    powMod overflows before the modulo ever runs

    result * b % m multiplies first and reduces second, so the full product has to fit in the machine word. Two values just under m can multiply to nearly m squared, which leaves 32-bit range once m passes about 46,341 and 64-bit range once m passes about 3 billion. That is the whole reason mulMod is in the code above: doubling and adding keeps every intermediate value under 2m, so the oversized product is never formed at all. It costs one pass over the bits of b, which is why it is used only when the modulus is genuinely large.

    When trial division stops, whatever is left is prime

    In the factorising loop, once the divisor d reaches the point where d * d exceeds the current n, that remaining n has no factor at or below its own square root, so if it is still above 1 it is prime and must be emitted. Forgetting this final push is the classic bug: 14 divides by 2 and then the loop exits with the 7 never reported. The guard has to be n > 1, not just a push, or a number whose factors all divide out, like 4, reports a spurious 1. A second trap in the same line is that d * d itself overflows for n near the top of the integer range. Comparing d <= n / d avoids it.

    Read more

    Next up

    Sieve of Eratosthenes

    Primes up to 30

    Next lesson: Sieve of Eratosthenes