Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

thanks

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

 
discard

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

Browse other questions tagged or ask your own question.