4
$\begingroup$

According to the well-know quadratic residue (QR) theory over integers, we know that it is hard to decide whether a given integer $m\in\mathbb Z_N$ is a quadratic residue (i.e., a square of another integer $x\in\mathbb Z_N$), without knowing the factorization of $N$.

Now, my question is: Without knowing the factorization of $N$, is it hard to decide whether a given matrix $M\in M_d(\mathbb Z_N)$ is a square of another matrix $X\in M_d(\mathbb Z_N)$ (i.e. $M=X^2\bmod N$) ?

In other words, when $d=1$, the so-called quadratic residue problem is a special case of my question. We know that it is hard when $d=1$, my question is: Is it hard for $d>1$?

Besides, is my following answer correct?

$\endgroup$
2
$\begingroup$

As for this question, is the following Karp redution correct?

Let the transfermation map $f:\mathbb Z_N\to M_2(\mathbb Z_N)$ be $f(m)=\left( m ~~~ 0\atop 0 ~~~ 1\right)$. Then, for a YES-instance $m=x^2\bmod N$, $$f(m)=\left( x ~~~ 0\atop 0 ~~~ 1\right)\left( x ~~~ 0\atop 0 ~~~ 1\right)\bmod N$$ is also a YES-instance naturally. For a NO-instance $m$, we need to prove $f(m)$ is a NO-instance too. Suppose $$f(m)=X^2\bmod N$$ be a YES-instance, then $$m=\det(f(m))=\det(X)^2\bmod N$$ becomes a YES-instance. This is a contradiction.

$\endgroup$
  • 1
    $\begingroup$ Of course it's correct, but it's not an answer to the question. It says if you could solve the matrix problem in polynomial time you could solve the scalar problem in polynomial time. But it doesn't tell you how to solve the matrix problem. $\det(M)$ being a square mod $N$ is necessary, but not sufficient, for $M$ to be a square mod $N$. $\endgroup$ – Robert Israel May 11 '18 at 7:21
  • 2
    $\begingroup$ @Robert Israel: Great response! If you really think my above reduction is correct, then my question is answered! According to the quadratic residue theory, we know that it is hard to determine whether a given integer $m$ is a quadratic residue (i.e. a square of another integer) modulo $N$, if the factorization is unknown. Therefore, we can conlude that, without knowing the factorization of $N$, it is also hard to determine whether a given matrix $M\in M_2(\mathbb Z_N)$ is a square of another matrix $X\in M_2(\mathbb Z_N)$. $\endgroup$ – Licheng Wang May 12 '18 at 10:49

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.