Search

Abstract: Efficient characteristic set methods for computing zeros of polynomial equation systems in a finite field are proposed. The concept of proper triangular sets is introduced and an explicit formula for the number of zeros of a proper and monic triangular set is given. An improved zero decomposition algorithm is proposed to reduce the zero set of an equation system to the union of zero sets of monic proper triangular sets. The bitsize complexity of this algorithm is shown to be for Boolean polynomials, where is the number of variables and is the number of equations. We also give a multiplication free characteristic set method for Boolean polynomials, where the sizes of the polynomials occurred during the computation do not exceed the sizes of the input polynomials and the bitsize complexity of algorithm is for input polynomials with variables and degree . The algorithms are implemented in the case of Boolean polynomials and extensive experiments show that they are quite efficient for solving certain classes of Boolean equations raising from stream ciphers. [Copyright &y& Elsevier]

Abstract: Given a multivariate quadratic polynomial system in a finite field , the problem MAX-MQ is to find a solution satisfying the maximal number of equations. We prove that the probability of a random assignment satisfying a non-degenerate quadratic equation is at least , where is the number of the variables in the equation. Consequently, the random assignment provides a polynomial-time approximation algorithm with approximation ratio for non-degenerate MAX-MQ. For large , the ratio is close to . According to a result by Håstad, it is NP-hard to approximate MAX-MQ with an approximation ratio of for a small positive number . Therefore, the minimal approximation ratio that can be achieved in polynomial time for MAX-MQ is . [Copyright &y& Elsevier]