Let us say there exists a permutation matrix $n \times n$ for some large $n$. Then, there are $n!$ possible permutations. If one to use brute-force to find the secret permutation among $n!$ possibilities, is there a parallel way to find such permutation?


  • $\begingroup$ How would a brute-force mechanism determine whether a particular permutation is the correct one? $\endgroup$ – poncho Jul 2 '13 at 0:32
  • $\begingroup$ Let us think of this as a condition statement and need to find some permuation matrix M. Regardless of how it is determined, is it possible to split the permutation generator so that each process work on portion of the all permutation possibilities? For example, searching for RSA modulo factor, one can take 10 processes so that each searches an interval. Thanks $\endgroup$ – Faith Jul 2 '13 at 0:52
  • $\begingroup$ To satisfy poncho's requirement I assume you run your outputs through an oracle. Your last comment is your answer: Yes you can, that's the way to parallelize tasks in general. In the case of RSA though you'll need a few more than 10 processors. If it's not RSA you're after however, give us some more info on your problem $\endgroup$ – rath Jul 2 '13 at 4:43
  • $\begingroup$ I don't understand why "matrix" is essential for your question. That is, couldn't a bit string of size n be ok for the same context? $\endgroup$ – Mok-Kong Shen Jul 2 '13 at 12:10

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.