Let $Ax=y$ a random undetermined linear system over $\mathbb{F}_2$, where $A\in \mathbb{F}_2^{m × n}$ and $y\in \mathbb{F}_2^m$. Suposse that it is known that there are at least $p$ solutions with Hamming weight less or equal that $r$. Where $r$ is small, for example slightly above of $m$. What is the best algorithm to find these solutions and what its worst case complexity?
It seems that there is not that algorithm. If you do known not any algorithm, could you help me, please, with the analysis of the next one. I trying a simple random algorithm
- Init a counter $c=0$
- Compute any particular solution $v$
- Get the right kernel of $A$ $K$.
- Let $k\in K$. If the Hamming weight of $k+v$ is less or equal than $r$ then $c=c+1$.
- If $c$ is equal $p$ stop, otherwise repeat step 4.
If I use the Gaussian Elimination method then the step 2 take $O(n^2m)$. In step 3, we use the PLUQ decomposition method to find the right kernel. According this work "Efficient Decomposition of Dense Matrices over GF(2)" that method take $O(n^{2.8})$. My problem is with the step 4 and 5. How can I find that complexity?