Computer Science – Symbolic Computation
Scientific paper
2010-11-30
Computer Science
Symbolic Computation
Scientific paper
Efficient characteristic set methods for computing solutions 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 solutions of a proper and monic (or regular) triangular set is given. An improved zero decomposition algorithm which can be used to reduce the zero set of an equation system in general form to the union of zero sets of monic proper triangular sets is proposed. As a consequence, we can give an explicit formula for the number of solutions of an equation system. Bitsize complexity for the algorithm is given in the case of Boolean polynomials. We also give a multiplication free characteristic set method for Boolean polynomials, where the sizes of the polynomials are effectively controlled. 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.
Gao Xiao-Shan
Huang Zhenyu
No associations
LandOfFree
Efficient Characteristic Set Algorithms for Equation Solving in Finite Fields and Applications in Cryptanalysis does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Efficient Characteristic Set Algorithms for Equation Solving in Finite Fields and Applications in Cryptanalysis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Characteristic Set Algorithms for Equation Solving in Finite Fields and Applications in Cryptanalysis will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-445176