Matpic
mathematics, in pictures
Concept

Cryptography

The study of what can be kept secret from an adversary with bounded resources. Its constructions are conditional by necessity: an unconditional one would separate complexity classes nobody has separated.

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

Four outputs are enough to find the rule. A row of 12 outputs of a linear generator, with the first 4 marked as given and the rest as predicted. The multiplier and increment recovered from the given ones reproduce every later output exactly.

Four numbers and the rule is yours

A linear generator can be solved. Given a few of its outputs, the multiplier and the increment fall out of two congruences, and every future output is then known exactly — which is a failure of a completely different kind from the lattice defect, and is not detected by any test of how evenly the points are spread.

computation · Pseudorandomness 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

Named alongside it

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

Modular arithmeticPseudorandomnessRandomnessComplexityFactoringInverseLinear systemNext bit testPredictionQuadratic residueReduction

All concepts