Given the matrix $\begin{bmatrix} r_{11}&\dots&r_{1n}\\ \vdots&\ddots&\vdots\\ r_{m1}&\dots&r_{mn} \end{bmatrix}\in\Bbb Z^{m\times n}$ with $0<r_{ij}<2^n$ and $a,q\in\Bbb Z$ with $a,q<2^n$ what is the complexity of deciding if there is a product of form $r_{1j_1}\cdot\dots\cdot r_{mj_m}\equiv a\bmod q$?

$\begingroup$ To clarify: the integers $j_k$ satisfy $1\le j_1,\dots,j_m\le n$ with repetitions allowed? $\endgroup$– Greg MartinMar 13, 2018 at 19:31

$\begingroup$ repetitions allowed. $\endgroup$– TurboMar 13, 2018 at 22:09

6$\begingroup$ If repetitions are allowed, then what is the purpose of a matrix (as this problem has nothing to do with linear algebra)? Why not formulate this problem in terms of given sets of numbers (forming first row of the matrix, forming second row, etc.)? $\endgroup$– Max AlekseyevMar 14, 2018 at 1:55
2 Answers
It's NPcomplete. We reduce from the 1in3 SAT problem; we're given a formula with $m$ variables and $k$ clauses; we'll output a matrix with $m$ columns and just 2 rows.
We start by computing prime numbers $p_i$ up to $p_k$.
Let $r_{c,1}=\prod_i p_i$, where $i$ goes through all indices of clauses which contain literal $x_c$, and $r_{c,2}=\prod_i p_i$ where $i$ goes through all indices of clauses which contain literal $\neg x_c$.
Clearly we can form $a=\prod_{i=1}^{k} p_i$ iff the 1in3SAT instance is satisfiable.
The product of all entries in the matrix is $a^3$ so we can take $q>a^3$ to get rid of the modulo.
Let $N=pq<2^n$ be a large integer, which is the product of two large primes. Generating relations of the form $$r_1r_2 \cdots r_m \equiv a \mod N$$ is equivalent to integer factorization. In particular, $\gcd(r_1r_2 \cdots r_m,N)\ne1 $ for many such relations, so a factor can be extracted. Therefore, these two problems have the same time complexity. Currently, integer factorization has deterministic time complexity of $O(N^{1/4})$ arithmetic operations, or subexponential probabilistic time complexity, see [1], [2].
[1] Carl Pomerance, Primes Numbers, SpringerVerlag, N. Y. 2000.
[2] Vanstone, Handbook of cryptography, 2000.