Adi Shamir 2026-11-05
Adi Shamir introduced a polynomial-interpolation construction for threshold secret sharing in 1979. In Shamir's secret sharing, a secret is the constant term of a random polynomial of degree less than over a finite field; shares are its values at distinct nonzero field elements. Any shares recover the polynomial and hence the secret.[ref]
Fewer than shares leave every possible secret equally compatible when the other coefficients are uniformly random. This is an information-theoretic threshold guarantee, rather than a claim that recovering the secret merely takes a long time. The construction makes distributed authorization and resilience to missing shares compatible. It requires enough field elements for all distinct share positions.
Figure 1.
Adi Shamir, portrait published by the Weizmann Institute
.
Affine line in a vector space Created 2026-10-06 Updated 2026-11-05
In a vector space over a field , an affine line is a translate of a one-dimensional vector subspace. Its direction is that vector subspace, so multiplying by a nonzero scalar preserves the direction. Over a finite field of size it contains exactly distinct points. This usage concerns affine subsets of vector spaces, rather than the affine line as an affine scheme.
Akihiro Munemasa 2026-11-05
Akihiro Munemasa connects finite geometry, quadratic forms and algebraic combinatorics. His author-written notes The geometry of orthogonal groups over finite fields by Akihiro Munemasa develop geometric objects and associated graphs from quadratic forms over finite fields. The preface makes the purpose explicit: the geometry supplies nontrivial examples for studying graph symmetries.[ref]
For a concrete comparison over , consider and . The first vanishes on both coordinate axes, giving nonzero isotropic vectors. The second vanishes only at : a nonzero square is , and in . Thus equal-dimensional nondegenerate quadratic forms can have different Witt indices, here one and zero. The existence or absence of totally isotropic subspaces changes the incidence geometry built from the form. Munemasa's notes turn these algebraic distinctions into explicit geometric and combinatorial constructions.[ref]
Algebra Created 2026-09-24 Updated 2026-10-13
Algebra studies equations, algebraic operations, and the structures that make their rules work. Its elementary side expresses unknown quantities through variables and transforms mathematical expressions; its structural side asks which arguments apply to whole families of groups, rings, fields, and vector spaces. The useful step is identifying exactly which properties a calculation needs, so that it can be reused in a new setting.
For example, the polynomial equation over the real numbers factors as , giving roots and . The distributive property justifies the factorization, while the absence of zero divisors justifies concluding that one factor must vanish. Over the finite field , the same integer coefficients reduce to , with roots and . The symbols alone do not specify the arithmetic: the coefficient field is part of the problem.
In a ring with zero divisors, a familiar step can fail. Modulo , all four residue classes satisfy . For , the factorization holds modulo , yet neither factor is zero. This is why the field hypothesis is useful when reasoning about roots of a polynomial, and why solving an equation over the integers, over the real numbers, or in modular arithmetic can give different answers.
The structure is also useful beyond scalar arithmetic. Matrix multiplication composes linear maps, and multiplication in a group can compose symmetries. These operations need not be commutative, but associativity still permits a product of three transformations to be regrouped. A theorem depending only on associativity, an identity element, and inverse elements can apply to many different groups at once. A homomorphism identifies which operations survive when one structure is mapped to another.
Historically, al-Khwārizmī's treatise organizes equations involving squares, unknown quantities, and numbers. Frederic Rosen's 1831 English translation includes the calculation now written and geometric explanations for completing the square. In modern notation, gives or ; the historical treatment seeks the positive quantity . This illustrates both continuity of a computational idea and a difference in the permitted quantities. [ref]
Arithmetic geometry 2026-11-05
Arithmetic geometry studies polynomial equations using both algebraic geometry and number theory. The coefficient arithmetic matters: a geometric object may have real points while having no integer or rational points of the required kind.
For example, has real solutions, but no solutions in the integers. A square is congruent to zero or one modulo four, so a sum of two squares cannot be congruent to three. Such polynomial congruences modulo a prime or prime power can therefore obstruct the existence of global arithmetic solutions.
In the language of schemes, an object over has fibres over prime numbers that are varieties over finite fields, together with a generic fibre over . Comparing these fibres links the geometry of curves and abelian varieties to their arithmetic. Local solvability need not guarantee global solvability; the passage between these questions is a central source of structure and difficulty.
BCH code Created 2026-09-24 Updated 2026-11-05
Let be a finite field, let be coprime to , and choose an element of multiplicative order in an field extension. A BCH code of length , starting exponent , and design distance is the cyclic code whose generator polynomial of a cyclic code is
where is the algebraic minimal polynomial of over . Equivalently, is the least-degree monic polynomial over the base finite field vanishing at consecutive powers. This least-degree condition distinguishes the BCH code from its proper cyclic code subcodes with additional zeros. The BCH bound gives minimum Hamming distance at least .
For example, over the field with two elements, let and let be a polynomial root of . The roots and have the same algebraic minimal polynomial, so and give , a Hamming code of length seven.[ref]
Berlekamp polynomial factorization algorithm Created 2026-10-20 Updated 2026-11-05
For a monic squarefree polynomial , the Berlekamp polynomial factorization algorithm computes the fixed space of the Frobenius map on :
This is a vector space over , obtained as the kernel of a matrix minus the identity. If has distinct irreducible factors, the Chinese remainder theorem identifies with , so its dimension is .
A nonconstant element of separates factors through for . Repeating these splits produces the irreducible factors. Repeated factors require an initial squarefree factorization step; the fixed-space dimension statement assumes squarefreeness. The method converts polynomial factorization into linear algebra over a finite field.
For odd , multiplication by two permutes the residues modulo . Its orbit through is the binary cyclotomic coset modulo an odd integer. If has order in a finite field whose field characteristic is two, the Frobenius automorphism sends to . Hence the minimal polynomial of an algebraic element over is . Its coefficients are fixed by Frobenius and lie in , and its degree is the orbit size. Thus a binary cyclic code containing one defining zero of a cyclic code must contain the full orbit as zeros.
Binary inner product Created 2026-09-28 Updated 2026-11-05
For vectors , the binary inner product is the bilinear form
Its value is the parity of the coordinates at which both vectors are one. For example, , whereas because in the finite field .
The terminology does not impose the positive definiteness axiom of a real or complex inner product. A nonzero vector can have zero self-pairing, as the second example shows. The form is nevertheless a nondegenerate bilinear form: a nonzero coordinate of is detected by pairing with the corresponding standard basis vector. This pairing defines orthogonality and dual codes in coding theory.
Binary linear code 2026-10-14
A linear code over the two-element finite field. Its dimension gives codewords. Its weight enumerator in the convention is symmetric in exactly when the all-ones word belongs to : adding that word complements every bit and replaces weight by . Conversely symmetry makes the coefficient of equal the coefficient of , which is one.
Block code 2026-10-14
A block code assigns source messages to words of a fixed length over an alphabet. Its codewords form a subset of that fixed-length word space; a binary block code uses the two-symbol finite field .
C2 field 2026-10-07
A field is a Ci field with the bound . Function fields of curves over finite fields are examples. The extra-variable construction in surjectivity of reduced norms over C2 fields makes this polynomial-solvability property useful for division algebras.
For a nonzero vector space with an infinite field or infinite basis, cardinality is the displayed maximum, since vectors are finite linear combinations of basis vectors. Over a finite field, infinite underlying size forces infinite dimension. Over a countably infinite field, every positive finite dimension is already countably infinite. The theory of infinite underlying spaces is therefore categorical in every infinite cardinal for a finite field, but only in uncountable cardinals for a countably infinite field.
Characteristic polynomials of AB and BA Created 2026-09-29 Updated 2026-11-05
For square matrices of the same size over any field,
If is invertible, , so the products are similar matrices. To cover singular , introduce an indeterminate and work over the rational function field . The matrix is invertible there, hence and have the same characteristic polynomial. Both sides are polynomials in , so specialize . This proof also works over a finite field; choosing infinitely many scalars in the original field would not.
Equal characteristic polynomials do not force the products to be similar. With and , but . Both have characteristic polynomial , while their minimal polynomials are and .
Ci field Created 2026-10-07 Updated 2026-10-14
A field is if every homogeneous polynomial of degree in more than variables has a nonzero zero. Algebraically closed fields are , finite fields are , and the Lang-Nagata theorem for Ci fields controls function-field extensions.
In exact classical identification of an unknown linear Boolean function , a function oracle call returns one bit . The query complexity is exactly for . Queries on the standard basis inputs reveal , proving sufficiency. For necessity, a depth- decision tree has at most answer histories and must distinguish hidden binary strings; hence , even with adaptive inputs. A reversible circuit that preserves and updates a known target by exclusive or reveals the same one bit per call.
There is also a useful linear algebra proof. Along a fixed history, the chosen inputs form the rows of a matrix over the two-element finite field, and the replies specify . If there are queries, the rank-nullity theorem gives a nonzero vector with . Then and give identical replies throughout this history. This also explains why adaptive choices cannot evade the bound: equal earlier replies force the same later choices.
Coding theory Created 2026-09-24 Updated 2026-10-18
Coding theory studies representations of messages that make decoding efficient, reliable, or compact. In channel coding, messages are mapped to separated codewords, so a corrupted word can still be recognized as coming from one particular message. In lossless source coding, a prefix code instead assigns short descriptions to frequent symbols. The objectives differ, but both exploit structure in the set of allowed words.
The simplest error-correction example sends as and as . If the receiver sees , at most one bit flip is consistent with , whereas two flips would be needed to obtain it from . A repetition code therefore recovers the original by taking the majority function of the received bits. The Hamming distance between the valid codewords is three: the spaces of one-error outputs around them do not overlap. This turns error correction into geometry in a discrete space.
The central tradeoff is between code rate and minimum distance. Additional separation makes correction possible but leaves fewer words available for messages at a fixed length. The Hamming bound counts disjoint error neighborhoods, while linear codes turn encoding and error detection into computations with matrices over finite fields. These connections explain why combinatorics, linear algebra, and probability theory all enter the subject.
Richard W. Hamming's Error Detecting and Error Correcting Codes appeared in the Bell System Technical Journal in April 1950, pp. 147–160. Its introduction motivates automatic correction through failures in digital computing, and its constructions go beyond detecting an error to identifying and correcting its location.[ref]
Complete Legendre-symbol sum Created 2026-09-29 Updated 2026-11-05
For an odd prime , the complete sum of the Legendre symbol is
Choose a quadratic nonresidue . Multiplication by permutes the finite field , while multiplicativity of the Legendre symbol gives . The sum is therefore equal to its own negative, and is zero. Equivalently, among the nonzero residue classes, exactly half are quadratic residues and half are quadratic nonresidues; the zero term contributes zero.
Computational number theory studies algorithms for arithmetic objects, including integers, finite fields, polynomials and algebraic number fields. Typical tasks are greatest-common-divisor computation, modular inversion, primality testing and integer factorization. The output may be an answer together with a certificate that can be checked independently.
For example, the extended Euclidean algorithm finds , certifying that the inverse of seven modulo twenty-six is fifteen. Modular exponentiation by repeated squaring computes with a number of modular multiplications proportional to the bit length of , instead of multiplying copies.
Input size is measured in bits, not by the numerical magnitude alone. An integer near has roughly bits, so an algorithm using time proportional to that integer can be exponential in its input length. Primality testing and complete factorization are distinct tasks; solving the former does not automatically supply the latter.
Fix finitely many prescribed cyclotomic classes for pairwise differences. Such patterns are realized in every sufficiently large compatible finite field. For already chosen coordinates, let count extensions with prescribed classes for . Averaging over all gives and, from the uniform two-class intersection estimate, . The Chebyshev inequality makes the fraction with tend to zero. Inductively each fixed pattern on coordinates occupies a positive proportion of all tuples, so some positive proportion have many extensions. This proves the pattern-existence claim without an unproved greedy-extension assumption.