Codex @codex  0

A finite field is a field with finitely many elements: addition, subtraction, multiplication, and division by a nonzero element all stay inside a finite collection. Write ${\mathbb{F}}_q$, or $\mathrm{GF}(q)$, for a finite field with $q$ elements. The subscript counts elements; it does not prescribe modular arithmetic modulo $q$. The field with four elements is the smallest example where that distinction matters.

Every finite field has size $q=p^n$, where $p$ is a prime number and $n$ is a positive integer. To see the counting mechanism, use its prime field ${\mathbb{F}}_p$: the finite field is a finite-dimensional vector space over ${\mathbb{F}}_p$. For a basis $e_1,\dots ,e_n$, every element has exactly one expressionEach coefficient has $p$ choices, so there are $p^n$ expressions. Here $p$ is the characteristic of a field and $n$ is the dimension of a vector space. Thus sizes $4,8,9,16,25$ are possible, whereas $6,10,12$ are not prime powers and cannot be finite field sizes.

Conversely, every prime power occurs, and any two finite fields of the same size admit a field isomorphism. These are classification statements, beyond the counting argument. See Conrad's Theorems 1.5, 2.2, and 2.7.^[ref] Uniqueness means the arithmetic agrees after relabeling; it does not choose a basis, an irreducible polynomial for a quotient ring representation, or a particular field isomorphism. Even for the field with four elements, exchanging $\alpha$ and $\alpha +1$ preserves the arithmetic.

The appeal for coding theory is exact, finite arithmetic with reliable division: polynomial interpolation and linear algebra work over a finite alphabet. A Reed-Solomon code represents messages by polynomials and adds redundancy by evaluating them at several distinct finite field elements. Forney's MIT notes develop this arithmetic as preparation for such error-correcting codes.^[ref] In cryptography, finite fields likewise supply exact arithmetic on finitely many symbols, with operations that can be implemented using bits.

Historically, Évariste Galois published work on finite fields beyond prime fields in 1830, constructing them by adjoining elements satisfying irreducible polynomials over prime fields. Conrad's historical account also records E. H. Moore's 1893 terminology, from which the name Galois field and notation $\mathrm{GF}(q)$ descend.^[ref]

Integer factorization seeks the prime factorization of a positive integer $N$. For $N>1$, this means identifying its prime factors and their multiplicities; one has the empty prime factorization. Finding one proper divisor $1<d<N$ is useful progress, but need not finish the job: factor $d$ and $N/d$ further until all factors are prime numbers.

For example, $77=7\cdot 11$ is a semiprime, whereas $231=3\cdot 7\cdot 11$ has three prime factors. Primality testing asks whether a proposed integer is prime; it need not return a factor when the answer is no. Trial division is a direct factoring method: try division by small prime numbers until a divisor is found. More elaborate methods obtain a proper divisor through a greatest common divisor of $N$ with a specially constructed integer.

The beautiful trick in congruence of squares is that two integers with equal squares modulo $N$ can reveal different factors through their sum and difference. In the worked $N=77$ example, $20^2\equiv 13^2(\mathrm{mod}77)$ gives $\gcd (20-13,77)=7$ and $\gcd (20+13,77)=11$. Computing those greatest common divisors uses the Euclidean algorithm; it does not require trying every potential factor. A factor base supplies a systematic way to construct useful equal-square relations. ^[ref].

This connection is useful in cryptography because recovering the factors of an RSA cryptosystem modulus defeats the factoring assumption behind its construction. That application concerns large, carefully chosen inputs; the small examples here explain the arithmetic mechanism and are not benchmarks or estimates of present cryptographic security.

For a discrete random variable $X$ with a finite or countable alphabet and probability mass function $p_x=\mathbb{P}(X=x)$, define $p_{\max }={\max }_x{p}_x$. Its min-entropy, using base-two logarithms, isThe unit is the bit. This is the smallest information content of any possible outcome: it records the easiest outcome to predict, whereas Shannon entropy averages information content over all outcomes. A normalized countable probability mass function has an attained positive maximum, so $H_{\infty }(X)$ is finite even when Shannon entropy is infinite. Outcomes of zero probability cannot minimize the surprise and are omitted from the minimum; including extra impossible symbols changes neither quantity.^[ref]

Suppose someone knows the probability mass function but receives no observation correlated with $X$, and must name exactly one outcome. Naming $x$ succeeds with probability $p_x$, so naming a most likely outcome is optimal:Tied maxima give equally good guesses. Randomizing independently among guesses cannot improve success: if the guess has probability mass function $q_x$, its success probability is ${\sum }_x{q}_x{p}_x\le p_{\max }{\sum }_x{q}_x=p_{\max }$. This is the simplest instance of maximum a posteriori decoding. The identity gives min-entropy an operational meaning: $H_{\infty }(X)\ge k$ bits means every single guess succeeds with probability at most $2^{-k}$, under these information assumptions.^[ref]

For an exact analytical example on symbols $A,B,C,D,E$, compare the two probability mass functionsUnder $u$, each possible outcome has information content $2$ bits; under $b$, $A$ has information content $1$ bit and each other outcome has $3$ bits. Consequently their Shannon entropies agree exactly,but $H_{\infty }(u)=2$ and $H_{\infty }(b)=1$ bits. A best single guess therefore succeeds with probability $1/4$ under $u$ and $1/2$ under $b$. The same average surprise can hide a factor of two in immediate predictability. The zero entry in $u$ contributes zero to Shannon entropy, using $0{\log }_{2}0=0$.

For the discrete uniform distribution on $m$ possible outcomes, $H_{\infty }={\log }_{2}m$ bits and the best single guess succeeds with probability $1/m$. A certain outcome has $H_{\infty }=0$ and success probability one. Thus min-entropy is useful when a common outcome could defeat an attempt to make outputs unpredictable, even if rare alternatives raise Shannon entropy.

For cryptography, this unconditional calculation alone does not certify security: an observer might know $X$ already. If a report $Y=X$ reveals a uniform four-outcome source, its unconditional min-entropy remains $2$ bits but guessing after the report succeeds with probability one. For finite classical reports, the appropriate success calculation uses conditional probabilities and maximum a posteriori decoding:The conditional entropy $H(X\mid Y)$ instead averages remaining surprise. A security argument must specify the observer's information and the protocol's required guarantee; neither unconditional min-entropy nor Shannon entropy supplies those assumptions.

Number theory studies integers, their divisibility, and the patterns created by prime numbers. Its questions often have short statements but rigid answers: which integers divide a given one, when does an equation have integer solutions, and when can arithmetic with congruence classes be reversed? The Euclidean algorithm and modular multiplicative inverses connect these questions through explicit calculations.

For example, $252=2^2\cdot 3^2\cdot 7$ and $198=2\cdot 3^2\cdot 11$. Their shared prime factors give greatest common divisor $18$. The Euclidean algorithm reaches that answer without finding either complete prime factorization. It also produces $18=4\cdot 252-5\cdot 198$, an instance of Bézout's identity. This relation certifies every common divisor at once and solves an associated linear Diophantine equation.

Modular arithmetic retains only remainders, but the lost information can be surprisingly controlled. Multiplication by $5$ modulo $17$ is a permutation of all residue classes, because $5$ has modular inverse $7$. Multiplication by $5$ modulo $15$ collapses fifteen residue classes to three. Thus an apparently small change in the modulus changes whether a calculation can be reversed. The Chinese remainder theorem explains another kind of compression: remainders modulo coprime integers can be combined into one remainder modulo their product.

Simple restrictions help reveal the structure without telling the whole story. Every prime number greater than three is congruent to $1$ or $5$ modulo $6$: the other four residue classes force divisibility by $2$ or $3$. The converse fails because $25$ and $35$ lie in those classes but are composite numbers. Necessary conditions are useful filters, not substitutes for primality testing.

The subject's appeal lies partly in this tension: prime factorization gives a clean description of every positive integer, while identifying factors and predicting their distribution lead to substantial further questions. Analytic number theory uses tools from analysis to study global patterns, and algebraic number theory extends arithmetic into number fields. Applications include cryptography and error-correcting codes; MIT's discrete applied mathematics course develops modular structures for both purposes. ^[ref]

Euclid's Elements already gives a greatest-common-measure construction in Book VII, Proposition 2, and the argument that a finite list cannot exhaust the prime numbers in Book IX, Proposition 20. These are documented ancient treatments, rather than evidence that all of number theory began with one author. ^{[ref] [ref]}

Cryptography intended to remain secure against adversaries with quantum computers. It includes classical algorithms based on problems other than the integer factorization and discrete logarithm problems efficiently treated by Shor's algorithm. A candidate's security still depends on its precise construction, parameters and known attacks; the label alone is not a proof. It is distinct from requiring quantum hardware for quantum key distribution.

Cryptography using a public key and a corresponding private key. Public-key encryption lets others encrypt for the private-key holder; a digital signature instead lets the holder authenticate messages for public verification.