On complexity of a combinatorial number theoretic problem? 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$?
 A: It's NP-complete. We reduce from the 1-in-3 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 1-in-3SAT
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.
A: 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, Springer-Verlag, N. Y. 2000.
[2] Vanstone, Handbook of cryptography, 2000.
