Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|improve this question
How would a brute-force mechanism determine whether a particular permutation is the correct one? – poncho Jul 2 '13 at 0:32
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 – Faith Jul 2 '13 at 0:52
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 – rath Jul 2 '13 at 4:43
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? – Mok-Kong Shen Jul 2 '13 at 12:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.