1

I'm making a tool that uses Cartesian product operations to work out every possible password given a source set of possible characters, and a length.

So, a source set might include 0-10, a-z and A-Z in one array, 62 characters in all.

At length 4, the Cartesian product will contain 4^62 passwords, all of length 4.

Is it possible for me to work out, given a source string, ie "a9BZ", what point it will occur in the Cartesian product?

Eric Lippert
  • 647,829
  • 179
  • 1,238
  • 2,067
Transmission
  • 1,219
  • 1
  • 10
  • 11
  • 1
    You can have 62^4 passwords of length 4, not 4^62. The number of combination depends on how you generate them (the code here I guess http://stackoverflow.com/a/22269999/1096117 ). It can be worked out from the answer we used (http://stackoverflow.com/a/9944993/1096117) – Julián Urbano Mar 08 '14 at 19:28
  • Suppose you have the characters 0-9 and you make the Cartesian product of four of them. Can you figure out what the index of `1234` is in the alpha-ordered set? It's the 1235th obviously. If you don't see why that has to be true, think about it until you do and then the answer to your question will appear obvious to you. – Eric Lippert Mar 08 '14 at 20:19
  • Whilst I agree with you Eric, my qualm is when you have a starting set like [ab] and you have a string of a's and b's about 1000 long. I'm just not sure how to transfer the logic. Would you start from the end of the string, and work backwards, adding the point in the source set [ab] that each character appears at, and doing some kind of power of each time? – Transmission Mar 09 '14 at 18:38
  • @Transmission: Well, suppose instead of `ab` you had `01`. Now your question is "which binary number is this?" If I gave you the string `1001`, how would you figure out what its index was in the set of binary numbers of length four? – Eric Lippert Mar 10 '14 at 21:30
  • Of course, you're right, I've just gotten it. I can just convert it to base 10. Thanks! – Transmission Mar 12 '14 at 21:19

1 Answers1

0

If you wouldn't have a string a9BZ but a98f and it wasn*t from a set of 64 characters, but from the well known hexadezimal set of 4-chars length, it would be easy, wouldn't it?

You would take the f as 15. Then 8*16 for the 8. Then 9*16*16 for the 9. Finally 16³*10 for the a and all added up.

In the same fashion you enumerate the ciphers and multiply by 64^position.

user unknown
  • 35,537
  • 11
  • 75
  • 121