Accelerating the factorization of multilinear boolean polynomials.

Tian Chen, Department of Mathematics, SFU

Friday July 14^th at 2:30pm in AQ 4102.

A multilinear Boolean polynomial f is a polynomial over GF(2) in which each variable has degree at most 1. Such polynomials arise in Boolean circuit optimization, yet their efficient factorization remains challenging. We present two Monte-Carlo algorithms that advance this problem.

Our first factorization algorithm assumes f is given in the sparse representation. It has algebraic complexity O(n²t) over a suitable extension field GF(2^k), where n is the number of variables and t is the number of terms of f. Our C implementation achieves substantial speedups over both the FDE and GCD algorithms of Emelyanov and Ponomaryov.

Our second algorithm assumes f is given by a black box for its evaluation. Here we apply our recently developed black box factorization algorithm CMBBSHL which is implemented in Maple and C. The black box representation allows us to reduce the parameter t to

T = smax ( ∑ #f_i + C(probe B) )

(which can be much smaller than t), where the f_i are the irreducible factors of f, smax is the maximum number of terms in any coefficient (in the highest ranking variable) in any factor, ∑ #f_i is the total number of terms in all irreducible factors, and C(probe B) is the cost of a single black box probe. This yields an overall algebraic complexity O(n²T). Our Maple and C implementation of our second algorithm is the fastest algorithm when T is much smaller than t.