Number Theory Basics

algorithmintermediateTime O(log n)Space O(1)

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.

Break 360 into primes. Try 2, then 3, then 4 and so on: divide it out as many times as it goes, and whatever is left over 1 at the end is prime itself.

How it runs, step by step

Break 360 into primes. Try 2, then 3, then 4 and so on: divide it out as many times as it goes, and whatever is left over 1 at the end is prime itself.
Finding the prime factors of 360 by dividing out each candidate in turn.
2 divides it. Peel off 2, leaving 180.
2 is a factor. The remaining number is 180.
2 divides it. Peel off 2, leaving 90.
2 is a factor. The remaining number is 90.
2 divides it. Peel off 2, leaving 45.
2 is a factor. The remaining number is 45.
3 divides it. Peel off 3, leaving 15.
3 is a factor. The remaining number is 15.
3 divides it. Peel off 3, leaving 5.
3 is a factor. The remaining number is 5.
Nothing up to the square root divides 5, so 5 is prime itself. It is the last factor.
5 has no smaller factor, so it is prime and is the last factor.
360 = 2 x 2 x 2 x 3 x 3 x 5. 6 prime factors.
360 factorizes as 2 times 2 times 2 times 3 times 3 times 5.

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.

1// Replace the larger number by its remainder against the smaller, until one of them is zero.2function gcd(a, b) {3  4  return 0;5}6

Ln 1, Col 16 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.

Topics covered

Where this is used

CryptographyTLS handshakes and RSA

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.

Standard librariesPython's fractions module

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.

DatabasesRedis Cluster hash slots

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.

PaymentsIBAN check digits

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.