Бінарні поліноми

Кожне відображення $f$ множини \{0,1\}^n $n$-вимірних бінарних векторів у $\{0,1\}$ називається булевою функцією $n$ змінних і позначається як f(x_n,x_{n-1},...,x_1). У криптографії деякі властивості булевих функцій є особливо цікавими. Позначимо через B(n,k) множину $n$-вимірних бінарних векторів, які містять $k$ одиниць. Ваше завдання полягає в тому, щоб для заданої булевої функції $f$ визначити кількість векторів (b_n,b_{n-1},...,b_1) з B(n,k), для яких виконується f(b_n,b_{n-1},...,b_1)=1.

Булева функція буде задана своїм (унікальним) поліномом за модулем $2$. У цих поліномах використовуються операції додавання та множення за модулем $2$, як показано в таблицях на Рис. 1. У поліномі функції будь-який добуток $m$ змінних x_{i1} x_{i2} ... x_{im} може бути присутнім або відсутнім. Таким чином, загальна форма полінома для $n$ змінних виглядає так:

де всі коефіцієнти a_j, j=0,1,...,N=2^n-1, є $0$ або $1$. Якщо коефіцієнт дорівнює $0$, ми опускаємо відповідний добуток, а якщо дорівнює $1$, ми просто не пишемо коефіцієнт. Наприклад, поліном булевої функції диз'юнкції $2$ змінних, наведений на Рис. 2, виглядає як 0+1 \cdot x_1+1 \cdot x_2+1 \cdot x_2x_1=x_1+x_2+x_2x_1.