For in the finite field , put . The multiplicative group of a finite field is cyclic, and character orthogonality expresses the number of th roots of as . The trivial character contributes , cancelling the term. Each of the remaining Gauss sums of Dirichlet characters has modulus , by the prime-field character Gauss sum identity. Consequently .
Prime field Created 2026-10-03 Updated 2026-10-14
The prime field of a field is its smallest subfield: the arithmetic forced upon us by the identity element . Every subfield must contain , its repeated sums, their additive inverses, and the multiplicative inverses of nonzero results. In characteristic zero these operations produce a copy of the rational numbers . In positive characteristic of a field , they produce a copy of , with addition and multiplication given by modular arithmetic.
For example, inside the field with four elements, repeated addition of gives . Thus its prime field is , and the other two elements cannot be reached by repeatedly adding . This is why a finite field need not consist entirely of ordinary integer residues: a larger finite field extends the arithmetic of its prime field with additional elements.
The positive characteristic of a field must be a prime number. If its least vanishing multiple of were with , then would exhibit zero divisors. The absence of zero divisors rules this out. The prime field supplies the scalars when viewing as a vector space; its basis then explains the possible sizes of a finite field.
Quadratic-equation satisfiability over F2 Created 2026-09-24 Updated 2026-11-05
Quadratic-equation satisfiability over F2 asks whether finitely many polynomials of polynomial degree at most two over the finite field have a common zero. Each unknown therefore takes one of the two truth values zero and one, with addition and multiplication performed modulo two.
A Boolean circuit can be encoded by introducing a Boolean variable for every logic gate output. An AND gate becomes , while a NOT gate becomes . Forcing the final output to one adds . All these constraints have degree at most two, and an assignment to the logic gate variables solves them exactly when it is a consistent accepting Boolean circuit evaluation.
The construction has polynomial size and reduces the Circuit satisfiability problem to this task. Guessing values and checking the displayed polynomials proves membership in NP, so the problem is NP-complete. This explains why allowing quadratic terms changes the computational picture from a system of linear equations solved by Gaussian elimination.
Quadratic form Created 2026-09-24 Updated 2026-10-14
A quadratic form on a vector space over a field is a function satisfying whose polar bilinear form of a quadratic form is a bilinear form. In finite dimension, it is represented in coordinates by a homogeneous degree-two polynomial, or by with a suitable matrix .
When the characteristic is not two, one may choose to be a symmetric matrix and recover it from . In characteristic two, the symmetric-matrix restriction would lose examples: has an upper-triangular representing matrix , while for a symmetric matrix has no cross term. Its polar form is , an alternating bilinear form. The distinction matters when studying quadratic forms over finite fields.[ref]
Quadratic Legendre-symbol correlation Created 2026-09-29 Updated 2026-11-05
For every odd prime , the Legendre symbol correlation satisfies
The small negative value measures an exact dependence between neighboring square tests; it is not obtained by treating them as independent.
Count the pairs satisfying . For each , their number is : it is one for zero, two for a nonzero quadratic residue and zero for a quadratic nonresidue. The total is therefore plus the desired sum.
Set and . Since is invertible in this finite field, this is a bijection onto the solutions of
Choose any . Then , uniquely determining and . There are exactly choices of . Hence , proving the correlation identity.
Quadratic polynomial Created 2026-10-14 Updated 2026-11-05
A quadratic polynomial in one variable over a field has polynomial degree two and the displayed form. Its roots of a polynomial satisfy a quadratic equation. The polynomial and its associated polynomial function are distinct objects: over a finite field, different polynomials can define the same function.
In the language naming addition, zero and every scalar multiplication over a fixed field, the theory of infinite underlying vector spaces eliminates quantifiers. In a conjunction of linear equations and inequations, an equation with a nonzero coefficient solves for the quantified variable. Otherwise the variable is excluded from only finitely many values, so infinitude supplies a witness. Disjunction and induction finish elimination. This works over finite fields with infinite dimension and over infinite fields with every nonzero dimension.
Quartic residue Created 2026-10-06 Updated 2026-11-05
A nonzero element of a finite field is a quartic residue when for some nonzero . If , the multiplicative group of a finite field is cyclic of order divisible by four, so the quartic residues form a subgroup of index four; equivalently .
A modular-addition quantum oracle for a linear function over the three-element finite field reveals its two coefficients in one query. Prepare the answer qutrit in , whose unit shift eigenvalue is . Quantum phase kickback produces a product of Fourier states labelled by the coefficients; inverse quantum Fourier transforms read both coefficients exactly.
Rational structure on an algebraic group Created 2026-10-14 Updated 2026-11-05
A rational structure over is a model over that finite field together with its identification after extension to . It determines a Frobenius endomorphism of an algebraic group, whose fixed points are the rational points. Conjugating a standard Frobenius by an algebraic group automorphism transports the rational structure, even if the automorphism is not itself rational for the original structure.
For row reduction with a parameterized right-hand side at , the nonzero reduced equations are
Column 3 has no pivot element, so is a free variable in a linear system. Taking gives every solution:
There is no further restriction on . Independent substitution into the original linear system gives
Conversely, the two reduced equations force exactly these coordinate formulas, so no solutions have been omitted. The same computation with zero right-hand side gives the kernel . Its dimension is one. The rank-nullity theorem appears here as : two pivot columns and one freely chosen coordinate account for the three unknowns.[ref]
In general a consistent linear system has solution set . Subtracting from proves this description in both directions. The particular solution places the affine subspace, and the kernel supplies its directions.[ref] Over the real numbers this example is an entire line; over the rational numbers the same formula uses rational . A free variable in a linear system over a finite field instead has only finitely many choices.
The pivot columns identify a different object: the original column space. Here they select
which form its basis, while . The corresponding reduced columns are and ; their linear span is a different plane. For example, every original output satisfies , but does not. Since is an invertible matrix, column linear relations survive even though the output vectors move. This is why choosing original columns at the reduced pivot positions works.
Reduced row echelon form Created 2026-10-14 Updated 2026-10-18
A row echelon form is in reduced row echelon form when every pivot element is one and is the only nonzero entry in its column.[ref] This extra reduction displays each pivot unknown directly in terms of the free variables in a linear system. The zero matrix also satisfies the definition: it has no pivot elements.
Every matrix has exactly one reduced row echelon form under elementary row operations, with its size and column order held fixed.[ref] Ordinary row echelon form is not unique: multiplying a nonzero row by two over the rational numbers keeps the staircase but changes the matrix. The reduced conditions remove that freedom.
For a fixed number of columns, each row space has a unique reduced matrix after zero rows are removed; at a fixed full size, the number of appended zero rows is also determined. Thus reduced row echelon form represents a vector subspace independently of the starting basis. This is the uniqueness used by Gaussian binomial coefficients to count vector subspaces over a finite field.
The fixed column order matters. Elementary column operations can change the row space, the kernel and the resulting reduced row echelon form. For instance, swapping the columns of over the rational numbers gives , whose reduced row echelon form is instead of . When solving a linear system, a column interchange also requires tracking the corresponding interchange of unknowns.
Reed-Solomon error correction Created 2026-10-14 Updated 2026-11-05
Let and let be distinct elements of a finite field . The Reed-Solomon code consists of evaluation vectors for polynomials of polynomial degree less than . It is a linear code with parameters and therefore a maximum distance separable code.
Indeed, evaluation is an injective linear map: a nonzero polynomial of polynomial degree at most cannot vanish at all evaluation points. The same polynomial root bound shows that every nonzero codeword has at least nonzero coordinates. Equality is attained by a polynomial vanishing at any chosen evaluation points. Thus the minimum Hamming distance is exactly , allowing correction of up to unknown symbol errors.
Primitive cyclic Reed-Solomon codes use all nonzero field elements, ordered as powers of a primitive root of unity. An arbitrary evaluation set need not give a cyclic code.
Relevance of independent self-sums Created 2026-09-24 Updated 2026-11-05
Let take values in the vector space over the two-element finite field. In this additive group, subtraction equals addition. Suppose is a C-relevant pair of random variables relative to , and take mutually independent copies . Then is -relevant to .
For a proof, let and take an independent representative of . The entropy submodularity for three independent sums gives
so the definition of Entropic Ruzsa distance yields
The last step is the Entropic Ruzsa triangle inequality. Apply the same argument to and add the inequalities.[ref]
The binary finite field hypothesis makes the displayed self-sum argument agree with the difference convention in Entropic Ruzsa distance. On a general abelian group, signs must be retained explicitly.
If the generator polynomial of a cyclic code has distinct roots with multiplicities , a word belongs to the code exactly when for , where is its Hasse derivative. The corresponding rows have entries for and zero otherwise. Expansion in a basis of the splitting field gives equations over the original finite field; an independent selection has rank .
For a cyclic code whose generator polynomial has distinct roots in a splitting field , the rows impose precisely the codeword conditions . Expanding each value in a basis of over the original finite field, then discarding dependent equations, gives a parity-check matrix over that field of rank . Alternatively choose one root from each Frobenius conjugate orbit and expand its value in the field it generates.
Root-evaluation syndrome for a cyclic code Created 2026-10-03 Updated 2026-11-05
Let be a polynomial root of the generator polynomial of a cyclic code over a finite field , viewed in an field extension. Every codeword satisfies , so a received polynomial has syndrome . A single-symbol error gives
To identify both value and position from this one syndrome, the maps must be injective over the allowed nonzero values and coordinate positions. Equivalently, the powers for distinct positions must not be proportional by a nonzero element of the base finite field. In the binary case , distinct powers suffice.
For nonbinary errors, distinct powers alone do not suffice. Over , take and two positions. Errors in position zero and in position one both evaluate to , although and are distinct. Additional syndromes or stronger conditions on the powers are then necessary.
Semisimple linear operator Created 2026-10-14 Updated 2026-11-05
A linear operator is semisimple if it becomes diagonalizable over an algebraic closure; equivalently, its minimal polynomial has no repeated root over that closure. If an invertible operator has finite order prime to the characteristic of a field, its minimal polynomial divides . The derivative is coprime to this polynomial, so is semisimple. Its invariant irreducible summands over a finite field become multiplication by scalars in suitable finite field extensions.
Shamir's secret sharing Created 2026-09-29 Updated 2026-11-05
Shamir's secret sharing distributes a secret in a finite field so that any of shares recover it, while fewer than shares reveal no information about it. Choose , distinct nonzero field elements , and independent uniformly distributed coefficients , independent of . Set
and give participant the pair . Any shares determine by polynomial interpolation, hence determine . Fewer than shares have a distribution independent of ; this is Perfect secrecy of Shamir's threshold scheme.[ref]
For example, over the finite field , a two-share threshold with secret and coefficient gives . The shares and recover and . Either share alone is compatible with every secret, and the uniform choice of makes its distribution independent of that secret.
A strongly universal hash family makes every ordered pair of outputs equally likely: for distinct inputs and arbitrary specified outputs ,
Thus the two outputs are independent random variables, each with the uniform distribution on a finite set. Adding the equal ordered pairs gives collision probability , so the family is also a universal hash family.
Here is a completely enumerable example. In the finite field , take the affine functions , using modular arithmetic modulo . Choose and as independent random variables, each with the uniform distribution on a finite set of all five finite field elements , including . There are equally likely hash functions. For , the ordered pair is . For instance gives ; gives . Every prescribed occurs exactly once, at .
Figure 1.
Enumerating all affine hash functions over the finite field with five elements
. Each cell shows the unique coefficient pair (a,b) producing the displayed outputs at 0 and 1. Removing a = 0 deletes the diagonal and leaves dependent outputs despite uniform individual values. Details.
Each row contains five choices, so each individual output has probability . Each cell has probability , and the five diagonal cells give collision probability . For any distinct , the same conclusion follows from and : a nonzero finite field element has a unique inverse. This is the beauty of the construction: two small random coefficients provide exact pair balance without choosing five unrelated values.
The example uses equal-sized input and output sets to make every choice visible; it illustrates the family definitions rather than compression. In a larger input set, a hash function cannot avoid all collisions into five buckets. What a universal hash family controls is the fraction of its members that collide on each fixed pair, rather than the existence of any collision anywhere.
Restricting to leaves permutations with zero collision probability for distinct inputs. Individual outputs remain uniform, but given , the four values other than each have conditional probability and has zero. Hence these outputs are not independent random variables: this is a universal hash family but not a strongly universal hash family. Finally, the full -member example contains five constant functions, with immediately visible collisions. Its pair guarantee concerns a random choice of hash function, and makes no claim of cryptographic collision resistance.