ALGORITHM TO DETERMINE THE FIXEDDEGREE POLYNOMIAL OF BOOLEANFUNCTION FOR CRYPTOGRAPHY

[摘要] Every Boolean function is uniquely defined by a polynomial modulo 2. The degree of a Boolean function is the degree of its defining polynomial. In cryptography, the Boolean functions of fixed degree played important role, for example, 1 or 2 degrees. Therefore, in finding algorithms that recognize properties of Boolean functions polynomials by their values vectors, it makes sense consider only algorithms that have lower complexity order. In this paper, we propose a linear complexity algorithm which determines the vector values a Boolean function given, it is a polynomial of fixed degree, and if so constructing this polynomial.

[关键词] Boolean function;fixed degree polynomial;algebraic normal form;numerical normal form