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$
$\endgroup$
3
-
$\begingroup$ To clarify: the integers $j_k$ satisfy $1\le j_1,\dots,j_m\le n$ with repetitions allowed? $\endgroup$– Greg MartinCommented Mar 13, 2018 at 19:31
-
$\begingroup$ repetitions allowed. $\endgroup$– TurboCommented Mar 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 AlekseyevCommented Mar 14, 2018 at 1:55
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
