On the AND Operation on Binary Multivariate Polynomial Ring

Abstract

On a binary multivariate polynomial ring F2 [x1; x2; :::; xn] we de ne AND operation as f ^ g := fg + f + g: The purpose of this de nition is speci cally associated with a solution method to binary multivariate nonlinear system, and even furthur connected to algebraic attack on a cryptosytem. In this case, every single polynomial in the ring can be considered as a Boolean object, then in symbolic computaion perspective that the polynomial can be represented as a set of integers and these integers represent monomials of the polynomial. With this point of view, we construct an algorithm to compute the AND operation and accelerated the performance using the idea of devide and conquer recurrence. By the same idea, an algorithm for solving binary multivariate nonlinear system is constructed as well. At the end of the paper, we give a speed analysis of the algorithms and also present some facts from the implementation aspect.