Efficient Prime Factorization of Logic Expressions

The set of multivariate boolean functions over the variables x₁, ..., x_m is considered as the set of multilinear polynomials with coefficients in [0,1] over the literals {unkeyable}. We denote this set of polynomials as [unkeyable], and call the set of polynomial operations over them algebraic operations. It is shown that these polynomials, called logic expressions, have a unique algebraic prime factorization. An O(n log ² n) algorithm to find this factorization is presented. An improvement to the algorithm is presented which may reduce its average-case complexity to O(n).