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
    Commented Jul 2, 2013 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
    Commented Jul 2, 2013 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
    Commented Jul 2, 2013 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$ Commented Jul 2, 2013 at 12:10


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.