  An improved characteristic set algorithm for solving Boolean polynomial
systems is proposed. This algorithm is based on the idea of converting all the
polynomials into monic ones by zero decomposition, and using additions to
obtain pseudo-remainders. Three important techniques are applied in the
algorithm. The first one is eliminating variables by new generated linear
polynomials. The second one is optimizing the strategy of choosing polynomial
for zero decomposition. The third one is to compute add-remainders to eliminate
the leading variable of new generated monic polynomials. By analyzing the depth
of the zero decomposition tree, we present some complexity bounds of this
algorithm, which are lower than the complexity bounds of previous
characteristic set algorithms. Extensive experimental results show that this
new algorithm is more efficient than previous characteristic set algorithms for
solving Boolean polynomial systems.
