Concept

Chinese remainder theorem

The fact that remainders modulo coprime numbers can be chosen independently and determine one remainder modulo their product. It lets a computation modulo a composite number be split into smaller computations modulo its factors and reassembled.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

One number, two dials: 3 and 5. A grid of remainder pairs, each cell holding the smallest number that leaves those two remainders.

Two dials at once

Watch one number on two clocks with different faces. If the faces share no factor, every pair of readings occurs exactly once — so two remainders name a number, and a hard calculation can be split into two easy ones.

number · Modular arithmetic

The walk x² + 1 modulo 101, drawn as the letter ρ. Starting at 2 and squaring and adding 1 modulo 101, the walk visits 8 values once on a tail and then runs round a cycle of 9 values for ever.

A collision that finds a factor

A walk through the remainders modulo a number must eventually repeat, and it repeats modulo each hidden prime factor long before it repeats modulo the number. Pollard saw that the earlier repeat can be detected without knowing the prime — and that its timing is the birthday problem, so the cost is the square root of the factor.

probability · Birthday problem

Named alongside it

The objects these essays reach for when they reach for this one.

Greatest common divisor Modular arithmetic Bijection Birthday problem Collision Counting two ways Cyclic group Factoring Iteration Lattice Modulus Periodicity

All concepts