Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleCharacteristic set algorithms for equation solving in finite fields
Author(s) Xiao Shan Gao, Zheng-Hai Huang
TypeArticle in Journal
AbstractEfficient 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 ( l 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.
KeywordsCharacteristic set, Finite field, Boolean polynomial, Proper triangular set, Single exponential algorithm, Stream cipher
URL http://www.sciencedirect.com/science/article/pii/S0747717111002185
JournalJournal of Symbolic Computation
Pages655 - 679
NoteAdvances in Mathematics Mechanization Mathematics Mechanization
Translation No
Refereed No