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.