I know that thanks to Shor's algorithm, integer factorisation is easy on quantum computers, yet hard on classical computers.

But what if I have two MATRICES, A and B, and compute the product N = A * B. Can a quantum computer, or a classical computer, find A and B without brute-forcing all possibilities?

Furthermore, is it possible to test the "divisibility" of N by some matrix M?

This is assuming that the elements of the matrices can only ever be integers (perhaps with some modulus) and the A and B are "prime", defines as: a matrix M is prime if there is no possible set of non-identity matrices that multiply to M.

I'm thinking about whether this could be useable as a quantum-resistant cryptographic accumulator.

  • 2
    $\begingroup$ det N = det A * det B. So finding A and B is at least as hard as factoring det N. $\endgroup$ – Luca De Feo Jan 13 '18 at 14:41
  • 2
    $\begingroup$ And your definition of "prime" is not very meaningful. Note that the identity is not "prime", as $\left(\begin{smallmatrix}0&1\\1&0\end{smallmatrix}\right)$ squared is equal to it. It would probably be more usfeful to ask that det A and det B are primes. $\endgroup$ – Luca De Feo Jan 13 '18 at 14:58
  • 2
    $\begingroup$ In the end, Gaussian reduction should prove that your problem is equivalent to factoring det N. However it is hard to give a definitive answer, since your question is vague about the exact definition of A, B and N. $\endgroup$ – Luca De Feo Jan 13 '18 at 15:06
  • $\begingroup$ Are we talking only about square matrices or not? $\endgroup$ – Florian Bourse Jan 15 '18 at 10:11
  • $\begingroup$ Yes, only square matrices. $\endgroup$ – user2894959 Jan 15 '18 at 12:12

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.