Setup
I have an applied math problem with a system, \begin{align*} Y = XA \end{align*} Where $Y\in\mathbb{Z}/2\mathbb{Z}^{100\times 1}, X\in\mathbb{Z}/2\mathbb{Z}^{100\times800}$ and $A\in \mathbb{Q}^{800}$. Although I would like to find an $A$ in the finite field $\mathbb{Z}/2\mathbb{Z}$. Where $\mathbb{Z}/2\mathbb{Z}$ is the finite field of $\{0,1\}$ which means the matricies $Y,X$ only contain the elements $\{-1,0,1\}$.
Question
How do I find an $A$ of this over-determined system with either integer, $\mathbb{Z}/p\mathbb{Z}$, or $\mathbb{Z}/2\mathbb{Z}$ coefficients?
Current Solution
To solve this system I am using rank-revealing QR factorization to find a solution, \begin{align*} XP &= QR\\ X_{reduced} &= XP_1 \end{align*} Where $P_1\in\{0,1\}^{100\times 100}$ is a permutation matrix that puts the 100 columns associated with the orthogonal basis of $X$ to make the resulting matrix $X_{reduced}\in \mathbb{Z}/2\mathbb{Z}^{100\times 100}$ square and full rank resulting in a solution $A$ that has rational coefficients.
Problem
If I just brute force tried to search for all permutations of columns in $X$ there are $10^{287}$ permutations. I need a closed form or reduced search method for finding a combination of columns that results in ideally some prime integer coefficient solution matrix $A$.