# The Knapsack Problem Given $\sum_{i=1}^n a_i\cdot X_i=c$ where $a_i,c\in\mathbb{Z}$, find a solution $(x_0,\ldots,x_n)\in\{0,1\}^n$. This is called [[Linear Diophantine equation]]. Note - There is efficient algorithm to solve this type of linear equation for integers but not for binary solution. - if n=128 this means that solving this in brute-force will require $2^{128}$ steps. Reference: [[@The Two Faces of Lattices in Cryptology]] ## Created 2024-10-14 06:31