Matpic
mathematics, in pictures
Concept

Reduction

A procedure turning any solution of one problem into a solution of another, so that the second is at least as hard as the first. It is how hardness is transferred, and every claim that a construction is secure is a reduction to something believed hard.

Named by 2 essays across one field — 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 A compass that will not change its opening. A segment longer than twice the compass's fixed opening, with the opening stepped along it 2 times and the remaining piece bisected by two arcs of that same opening.

The compass that will not open

Fix the compass at one opening and never change it. That looks like a serious loss — a circle of a given radius through a given point is the compass's whole job — and it turns out to cost nothing at all, for reasons that are arithmetic rather than geometric.

computation · Compass-only

Named alongside it

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

CircleCompassComplexityConstructible numberConstructionCryptographyFactoringMidpointModular arithmeticPseudorandomnessQuadratic residueRandomness

All concepts