Concept

Discrete logarithm

The exponent solving g to the power x equals h in a finite group, when one exists. It is easy to state, easy to check, and believed to be hard to compute in the groups cryptography uses — which is what a great deal of public-key cryptography rests on.

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

The non-zero elements of GF(16) as the powers of one of them. A ring of the field's non-zero elements in the order the powers of a primitive element produce them, beside a table of exponents.

Every element is a power of one of them

Pick the right element of a finite field and its powers run through every other non-zero element exactly once before returning to one. Multiplication becomes addition of exponents, and a table of q − 1 entries replaces the whole multiplication table.

computation · finite fields

A 4-bit register that visits all 15 nonzero states. The first 15 states of a 4-bit linear feedback shift register with taps at 4 and 1, with the bit that leaves the register at each step; the output shows every nonzero window of 4 bits exactly once.

A memory of four bits

A register holding four bits, shifting them along and adding two of them back, runs through all fifteen nonzero states before it repeats. Which two are added back is a question about a polynomial, and getting it wrong costs fourteen of the fifteen.

computation · de bruijn

Named alongside it

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

Finite field Primitive element Counting argument Cyclic group De bruijn sequence Fermats little theorem Group Modular arithmetic Periodicity Polynomial Pseudorandomness Recurrence

All concepts