1
$\begingroup$

Given a matrix $A\in M_d(\mathbb Z_N)$, is it hard to determine whether there exists another matrix $B\in M_d(\mathbb Z_N)$ such that $A=B^2\bmod N$? Suppose the factorization of $N$ is unknown and intractable.

More generally, how to find $B=\sqrt{A}\bmod N$ for given matrix $A$ such that $B=A^TA$?

$\endgroup$
  • 3
    $\begingroup$ I do not get the "such that $B=A^TA$" part of the question. Remarks: The question seems to ask for an extension of the Jacobi symbol to $M_d(\Bbb Z_N)$. On computing square roots in $M_d(\Bbb Z_N)$: demonstrably, for some $A$ it is difficult to find all $B$ with $A=B^2\bmod N$. Proof: consider finding all such $B$ for $A=\begin{pmatrix}x&0&\cdots&0\\0&0&\cdots&0\\\vdots&\vdots&\ddots&0\\0&0&\cdots&0\\\end{pmatrix}^2\bmod N$; solving that finds the integer square roots of any given $x^2\bmod N$, which implies the ability to factor $N$. $\endgroup$ – fgrieu May 9 '18 at 2:13
  • $\begingroup$ Thanks a lot! For the part of "$B=A^TA$", my means is that: $A$ might not be a square matrix, say $n\times m$-dimensions, then, $B=A^TA$ is in $n\times n$-dimension. $\endgroup$ – Licheng Wang May 9 '18 at 9:08
  • $\begingroup$ Does your suggestion implies the following Karp reduction from the so-called quadratic residue problem (QRP) to matrix-quadratic-residue problme (MQRP)? Suppose $f:\mathbb Z_N\to M_2(\mathbb Z_N)$ $$x\mapsto\left(x ~~~ 0 \atop 0 ~~~ 0\right)\bmod N.$$ For a yes-instance $x\in QR$ (i.e., $x=y^2\bmod N$ for some $y$), $$f(x)=\left(x ~~~ 0 \atop 0 ~~~ 0\right)=\left(y ~~~ 0 \atop 0 ~~~ 0\right)^2\bmod N$$ is also a yes-instance of MQRP. $\endgroup$ – Licheng Wang May 9 '18 at 9:24
  • $\begingroup$ For a no-instance $x\not\in QR$, we need to prove that there is no matrix $B$ such that $f(x)=B^2\bmod N$. By contrary, say there exists such a $B=\left(b_{11} ~~~ b_{12}\atop b_{21} ~~~~ b_{22}\right)$, then we have $\endgroup$ – Licheng Wang May 9 '18 at 9:28
  • $\begingroup$ But for a no-instance $x\not\in QR$, how to prove that there is no matrix $B$ such that $f(x)=B^2\bmod N$? Say, by contrary, say there exists such a $B=\left(b_{11} ~~~ b_{12}\atop b_{21} ~~~~ b_{22}\right)$, then we have $$b_{11}^2+b_{12}b_{21}=x$$ $$b_{11}b_{12}+b_{12}b_{22}=0$$ $$b_{21}b_{11}+b_{22}b_{21}=0$$ $$b_{21}b_{12}+b_{22}^2=0$$ We cannot encounter a contradition. So, it might be better to re-define $f$ as $x\mapsto \left(x ~~~ 0 \atop 0 ~~~~ 1\right)$. $\endgroup$ – Licheng Wang May 9 '18 at 9:38

Your Answer

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

Browse other questions tagged or ask your own question.