Characteristic set algorithms for equation solving in finite fields

摘要

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 O(/I~n) for Boolean polynomials, where n is the number of variables and l ≥ 2 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 O(n~d) for input polynomials with n variables and degree d. 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.