Matpic
mathematics, in pictures
Concept

Factoring

Writing a whole number as a product of primes, which is unique but can be hard to find. The difficulty of factoring large numbers underlies public-key cryptography, and the fastest methods look for a collision or a congruence of squares rather than dividing.

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

A scatter with no lines in it. 900 consecutive pairs from a generator that squares modulo a product of two primes. The points show no family of parallel lines, and an exhaustive search for a short relation between consecutive outputs finds none.

Randomness that has to be earned

A generator that resists prediction cannot be built out of a rule anybody can fit. It has to be built out of a computation believed hard to undo, and the belief is the load-bearing part — which makes cryptographic randomness a conditional statement rather than a construction.

computation · Pseudorandomness 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 The largest prime factor, as a power of the number. Share of n with log P(n)/log n ≤ s: at s=0.5, n≤10⁴ 0.268, n≤10⁷ 0.272, Dickman 0.307; median e^(−1/2) = 0.6065; largest gap at 10⁷ 0.061.

The largest prime in a typical number

Count a number's prime factors and the answer is about log log n. Ask instead how big the largest one is, and the answer is a power of n with a law of its own: half of all large numbers have a prime factor above n^0.6065, and the share whose primes all stay below n^(1/u) is Dickman's ρ(u), a function defined by its own past. The same law governs the longest cycle of a random shuffle, and there it arrives at once; for the numbers themselves, at ten million, it is still visibly on its way.

number · Unique factorisation

Named alongside it

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

Modular arithmeticAsymptoticsBirthday problemChinese remainder theoremCollisionComplexityCryptographyCycleDifferential equationGreatest common divisorIterationLargest prime factor

All concepts