Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10325826 | Journal of Symbolic Computation | 2012 | 25 Pages |
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 O(ln) 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(nd) 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Xiao-Shan Gao, Zhenyu Huang,