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 2 essays across 2 fields — each of them below, with the objects they name alongside it.

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

Named alongside it

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

Modular arithmetic Birthday problem Chinese remainder theorem Collision Complexity Cryptography Greatest common divisor Iteration Pigeonhole principle Pseudorandomness Quadratic residue Randomness

All concepts