1
$\begingroup$

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$?

$\endgroup$
3
  • $\begingroup$ To clarify: the integers $j_k$ satisfy $1\le j_1,\dots,j_m\le n$ with repetitions allowed? $\endgroup$ Mar 13, 2018 at 19:31
  • $\begingroup$ repetitions allowed. $\endgroup$
    – Turbo
    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$ Mar 14, 2018 at 1:55

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.