Algebraic normal form

In Boolean logic, 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, 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.

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. Propeties of nonlinear feedback shift registers can also be deduced from certain properties of the feedback function in ANF.