# can a quantum or classical computer perform “MATRIX factorisation”?

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.

• det N = det A * det B. So finding A and B is at least as hard as factoring det N. – Luca De Feo Jan 13 '18 at 14:41
• 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. – Luca De Feo Jan 13 '18 at 14:58
• 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. – Luca De Feo Jan 13 '18 at 15:06
• Are we talking only about square matrices or not? – Florian Bourse Jan 15 '18 at 10:11
• Yes, only square matrices. – user2894959 Jan 15 '18 at 12:12