Skip to content

Algebraic normal form

The unique multilinear polynomial over GF(2) representing a Boolean function as an XOR of square-free AND monomials and an optional constant.

Version
v1 · 2026-09-28 · History
Domain-specific #
7918
Domain group
Formal Sciences
Origin domain
Mathematics
Subdomains
Boolean Algebra, Finite Fields → Mathematics

Core Idea

Algebraic normal form (ANF) represents a Boolean function as a polynomial over GF(2). Variables are multiplied to form square-free monomials—Boolean conjunctions—and those monomials plus an optional constant are combined by XOR, the field's addition.

Because coefficients are only zero or one, a monomial is either absent or present. Because Boolean inputs satisfy x²=x, higher powers collapse. Duplicate monomials cancel under XOR, yielding a multilinear reduced polynomial.

Every Boolean function has a unique ANF. That makes it useful for equality testing, cryptographic analysis, and circuit representation, but its compactness varies: a function simple in another basis can have many ANF monomials. It is not DNF, where OR replaces XOR.

How would you explain it like I'm…

The Lamp-Flipping List

Imagine a lamp that some teams of switches can flip. Each team flips the lamp only when every switch in that team is on. You start with the lamp off, or sometimes on, and each team that's all on flips it once more. Algebraic normal form writes any on-off rule as a list of which teams flip the lamp, and each rule has only one such list.

AND Groups Joined by XOR

A Boolean function takes some yes/no inputs and gives a yes/no answer, like a rule deciding if a light turns on from several switches. Algebraic normal form writes any such rule in one standard way. You make groups of inputs joined by AND (all must be on), and then combine the groups with XOR, which flips the answer each time a group is on. You can also include a constant 1 at the start. Every Boolean rule can be written like this in exactly one way, so two rules are the same if and only if their lists match. This is different from the more familiar way of combining groups with OR.

Unique GF(2) Polynomial Form

Algebraic normal form (ANF) writes a Boolean function as a polynomial over GF(2), the two-element field where 1 + 1 = 0. Multiplication in that field is AND and addition is XOR. Each term is a product of distinct variables, called a monomial, and the function is the XOR of some of these monomials plus possibly the constant 1. Because every input is 0 or 1, x² = x, so no variable ever needs to appear squared, and because x XOR x = 0, repeated terms cancel. What remains is a unique reduced polynomial for each function, so two functions are equal exactly when their ANFs match. It is used in cryptography and circuit design, though some simple functions need a lot of terms in ANF. It is not the same as disjunctive normal form (DNF), which combines terms with OR.

 

Algebraic normal form represents a Boolean function f: {0,1}^n → {0,1} as a polynomial over GF(2). Monomials are products of distinct variables, i.e., conjunctions, and the polynomial is the XOR (field addition) of a set of such monomials plus an optional constant. Since coefficients are 0 or 1, each monomial is simply present or absent; since Boolean inputs satisfy x² = x, higher powers collapse; and since duplicate monomials cancel under XOR, the result is a reduced multilinear polynomial. Every Boolean function has a unique ANF, which supports equality testing, cryptographic analysis such as reasoning about algebraic degree, and circuit representation. Its size is basis-dependent: a function that is compact in another representation may need many ANF monomials. ANF must not be confused with DNF, where OR replaces XOR and uniqueness does not hold in the same way.

Structural Signature

Sig role-phrases:

  • Boolean variables. Take values in GF(2), identified with false/true. Constitutive carrier. If altered: Non-Boolean domains require another polynomial-function theory.
  • square-free monomials. Multiply distinct variables, corresponding to conjunction. Constitutive terms. If altered: Repeated exponents collapse under x²=x.
  • GF(2) coefficients. Include or omit each monomial and optional constant. Constitutive weights. If altered: Ordinary integer coefficients do not define ANF.
  • XOR sum. Combines monomials by addition modulo two. Identity-bearing operation. If altered: OR between terms yields another normal form.
  • function equivalence. Requires the polynomial and Boolean formula to agree on every input. Constitutive semantics. If altered: Syntactic resemblance without truth-table equality is insufficient.
  • canonical uniqueness. Gives one reduced polynomial for each Boolean function. Characteristic guarantee. If altered: Leaving cancellable duplicates destroys normal form.

What It Is Not

  • Not disjunctive normal form. ANF combines products by XOR rather than OR.
  • Not ordinary polynomial algebra. Coefficients and addition are modulo two and variables are Boolean.
  • Not any XOR expression. Terms must be reduced to square-free monomials with duplicates canceled.
  • Not always compact. Canonical uniqueness does not guarantee few terms.

Scope of Application

ANF applies wherever a Boolean function is analyzed through its unique GF(2) multilinear polynomial.

  • Boolean algebra. Provides a canonical function representation.
  • Cryptography. Studies algebraic degree and nonlinear terms.
  • Logic circuits. Translates functions into XOR–AND structure.
  • Coding theory. Uses GF(2) polynomial relations.
  • Formal verification. Compares functions through canonical coefficients.

Clarity

The representation separates three operations often blurred in logical notation: AND is multiplication, XOR is addition, and ordinary OR must be translated. Its uniqueness applies to the represented function after GF(2) reduction, not to arbitrary written formulas.

Manages Complexity

A truth table with 2^n rows becomes a set of monomial coefficients. The canonical form supports comparison and algebraic manipulation while exposing degree and interaction structure that a syntactic Boolean formula can hide.

Abstract Reasoning

  1. Fix Boolean variables and interpret values in GF(2).
  2. Convert logical operations or the truth table into polynomial coefficients.
  3. Reduce powers using x²=x and coefficients modulo two.
  4. Cancel duplicate monomials under XOR and order the remainder canonically.
  5. Verify function equality on all assignments or through a valid transform.

Knowledge Transfer

ANF transfers literally across Boolean functions, circuits, and cryptographic mappings using the same GF(2) semantics. Calling an ordinary polynomial 'algebraic normal form' outside this quotient structure is not literal transfer.

Examples

Canonical

The Boolean function a OR b becomes a ⊕ b ⊕ ab. On inputs 00, 01, 10, and 11 the polynomial matches OR, and its three distinct square-free monomials form the unique ANF.

Mapped back: Boolean variables → a,b; square-free monomials → a,b,ab; GF(2) coefficients → all one; XOR sum → three-term parity sum; function equivalence → matches OR truth table; canonical uniqueness → fully reduced.

Applied / In Practice

A cryptanalyst expands an output bit of an S-box into ANF and reads the highest monomial degree and interaction terms. The polynomial represents the bit exactly; degree is then a derived property rather than a claim about the whole cipher.

Mapped back: Boolean variables → S-box input bits; square-free monomials → input products; GF(2) coefficients → presence vector; XOR sum → output polynomial; function equivalence → exact output-bit mapping; canonical uniqueness → one coefficient set.

Structural Tensions

T1: canonical comparison vs. representation size. Uniqueness simplifies equality while some functions expand into many monomials. Diagnostic: Is canonicality or compact implementation the immediate goal?

T2: logical intuition vs. GF(2) arithmetic. Familiar OR/NOT syntax does not map symbol-for-symbol to XOR–AND algebra. Diagnostic: Were operations translated under the correct field semantics?

Structural–Framed Character

ANF is strongly structural. Field operations, Boolean idempotence, and function equivalence determine the representation independently of application. Its character: a unique GF(2) coordinate system for Boolean functions.

Structural Core vs. Domain Accent

Skeletal core. Express an object uniquely as coefficients over a complete basis and reduce under its algebraic identities.

Domain-bound accent. Boolean variables, GF(2), XOR, AND monomials, and algebraic degree specify ANF.

Why not prime. Canonical representation is broader; ANF is one exact finite-field normal form.

This entry is a kind of Polynomial.

  • Related — representation. ANF maps a Boolean function into a polynomial medium with exact fidelity.
  • Related — normal form. Reduction yields a canonical member of the equivalence class.

Relationships to Other Abstractions

Local relationship map for Algebraic normal formParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Algebraic normal formDOMAINDomain-specific abstraction: Polynomial — is a kind ofPolynomialDOMAIN

Current abstraction Algebraic normal form Domain-specific

Parents (1) — more general patterns this builds on

  • Algebraic normal form is a kind of Polynomial Domain-specific

    It is a multilinear polynomial normal form over GF(2).

Hierarchy path (1) — routes to 1 parentless root

Neighborhood in Abstraction Space

Algebraic normal form sits in a moderately populated region (47th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Polynomials & Algebraic Invariants (20 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With

  • Disjunctive normal form. Tell: Are product terms combined by OR or XOR?
  • Reed–Muller expansion. Tell: Is positive polarity fixed and equivalent to ANF, or are complemented literals admitted?
  • Ordinary polynomial. Tell: Are coefficients and evaluation in GF(2) with Boolean idempotence?
  • XOR circuit. Tell: Has the expression been reduced to the unique function form?

References

  • Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Algebraic_normal_form (revision 1368722504).
  • Preserved source candidate: http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=sm&paperid=7433&option_lang=eng
  • Preserved source candidate: https://web.archive.org/web/20171012193119/http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=sm&paperid=7433&option_lang=eng
  • Preserved source candidate: http://www.wolframalpha.com/input/?i=simplify+1+xor+a
  • Preserved source candidate: http://www.wolframalpha.com/input/?i=%28a+xor+b%29+and+%28c+xor+d%29+in+anf
  • Preserved source candidate: http://www.wolframalpha.com/input/?i=simplify+a+xor+b+xor+%28a+and+b%29
  • Preserved source candidate: http://mathworld.wolfram.com/Rule102.html
  • Preserved source candidate: http://mathworld.wolfram.com/Rule60.html
  • Preserved source candidate: http://encyclopediaofmath.org/index.php?title=M%C3%B6bius_inversion&oldid=50404

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.