How to solve a system of quadratic equations over finite fields?

Question

Hello!

Let $m$ be an odd positive integer. Let $r$ be the smallest extension order of finite field $GF(q)$ that the $m$-th roots of unity are in $GF(q^r)$. For instance, it can be assumed that $q = 2$.

Let $\mathbf{d}_i$, $1 \le i \le m$ be unknown $k$-dim vectors over $GF(q)$. Let $G$ be given $k \times l$ matrix over $GF(q)$. Let $\mathbf{y}$ be unknown $l$-dim vector over $GF(q^r)$. Let $H$ be $s \times m$ matrix over $GF(q^r)$ of full rank over $GF(q^r)$.

I have to find unknown non-zero vectors $\mathbf{d}_i$, $1 \le i \le m$ and $\mathbf{y}$ so the following equation vanishes: $(\mathbf{d}_1^T G \mathbf{y}, \mathbf{d}_2^T G \mathbf{y}, \ldots, \mathbf{d}_m^T G \mathbf{y}) H^T = 0$. How it can be done?

Thank you very much!

Answer 1

As others have noticed, this reduces to the problem of finding a non-zero $m\times k$ matrix $D$ such that $HDG$ has a non-trivial kernel.

If $l\ge 2$, you can take all the $\mathbf{d}_i$ equal but nonzero, so that $D$ has rank $1$ and $HDG$ has rank at most $1$, and $HDG$ has a non-trivial kernel.

If $l=1$, the problem is equivalent to $HDG=0$, which can be solved by linear algebra.

Answer 2

So, it sounds like the problem can be reduced to:

Given matrices $H,G$, find a non-zero $m \times k$ matrix $D$ such that the $s \times l$ matrix $HDG$ has a non-trivial kernel.

Of course, once you find such a matrix $D$, it is easy to find a non-zero vector $y$ that is in its kernel (by linear algebra), so the task is to find such a $D$.

If $s \le l$, this problem is probably easy. If you pick $D$ randomly, then with non-trivial (some constant $> 0$) probability, $HDG$ will have non-trivial kernel, and you can quickly test whether this is the case, so you will only need to try a constant number of random matrices $D$.

If $s > l$, I don't know if there is a better solution.