Algebraic normal form

From Wikipedia, the free encyclopedia

In boolean logic, the algebraic normal form (ANF) is a method of standardizing and normalizing logical formulas. As a normal form, it can be used in automated theorem proving (ATP), but is more commonly used in the design of cryptographic random number generators, specifically linear feedback shift registers (LFSRs). A logical formula is considered to be in ANF if and only if it is a single algebraic sum (XOR) of one or more conjunctions of one or more literals. ANF is also known as “Zhegalkin polynomial” (Russian: полином Жегалкина) and as “Positive Polarity (or Parity) Reed-Muller” expression.

Putting a formula into ANF makes it easy to identify linear functions, as is needed for linear feedback in LFSRs: a linear function is one that is a sum of literals. Properties of nonlinear feedback shift registers can also be deduced from certain properties of the feedback function in ANF.

The general ANF can be written as:

$f(x_1, x_2, \ldots , x_n) = \!$	$a_0 + \!$
	$a_1x_1 + a_2x_2 + \ldots + a_nx_n + \!$
	$a_{1,2}x_1x_2 + a_{n-1,n}x_{n-1}x_n + \!$
	$\ldots + \!$
	$a_{1,2,\ldots,n}x_1x_2\ldots x_n \!$