Bases over the field GF(2) generated by the schur - hadamard operation

The paper deals with the problem of constructing, describing and applying bases of vector spaces over the field GF(2) generated by the componentwise product operation up to degree d. This problem “Bases” was posed as unsolved in the Olympiad in cryptography NSUCRYPTO. In order to give a way to solve this problem with the Reed - Muller codes, we define the generating family F as a list of all string i in a true table under condition: the word x_i¹ , . . . , x_i^s has Hamming weight not superior d. The values of coefficients of function f are determined recurrently, as in the proof of the theorem on ANF: the coefficient before composition for subset T (cardinality does not exceed d) in the set { t¹ , . . . , t^s } of arguments is determined as the sum of the values of f and the values of the coefficients for the whole subset R Q T . Hence, for all s,d, s d > 1, there is a basis for which such a family exists, and the construction of the bases is described above. We propose to use general affine group on space F^s, F = GF(2), for obtaining the class of such bases in the condition of the problem.

Keywords

Authors

References