Research On Solving Algebraic Equations And Its Aplications

There are many relations between solving algebraic equations and actual problems in cryptography.For example,algebraic attack which becomes a hot topic in cryptography recently makes many scholars pay much attention to the solving of algebraic equations,and some properties of perfect nonlinear functions can be described and analyzed by the indefinite equation systems,and solving algebraic equations is also related to other cryptographic problems such as computing the linear complexity of stream sequences.In this paper,we discuss the solving approaches and applications of some kinds of algebraic equations related to the actual problems of cryptography.The properties of the transition matrix from orthogonal basis to monomial basis of Boolean functions are discussed firstly.We present an effective method for calculating the transition matrix,and give a new algorithm for solving Boolean function equation systems.The new algorithm does not depended on the difference of the number of variants and the number of equations,the algorithm complexity is m×2^1.59n-2ⁿ,where n denotes the number of variants and m denotes the number of equations.Perfect nonlinear functions have important applications in the design and analysis of cryptography.Claude Carlet and Cunsheng Ding have given some quantitative descriptions about the perfect nonlinear function on general abelian group by using the indefinite equation system.We present the general expression of solutions for the indefinite equation system corresponding to the perfect nonlinear functions from abelian group of order n to abelian group of order three,and we prove that the general expression of solutions must have nonnegative integer solutions when n≡3(mod18) and n/3 is prime.At the same time we present that the sufficient and necessary conditions which the indefinite equation system corresponding to the perfect nonlinear functions from abelian group of order n to abelian group of order four is solvable are n=16l²,l∈N.Linear complexity and k-error linear complexity of stream sequence are two important conception in stream cipher.The relation of linear complexity and k-error linear complexity of stream sequence is discussed in the firth chapter,then we present a inequality.And we bring forward the conception of local linear complexity.Finally,we compute the local linear complexity of one kind of stream sequence with special period.