4 ms·

> Turns out that an even easier way is just to assign 128 bits of randomness 52! is roughly 2^226. You cannot address all 2^226 positions with a 2^128 address

> Turns out that an even easier way is just to assign 128 bits of randomness 52! is roughly 2^226. You cannot address all 2^226 positions with a 2^128 address generated from 2^64 seed.

rcxdude 1y ago
it's 128 bits per card. That's vastly more than 226 bits.
- amluto 1y ago
  You could use something like 12 bits of randomness per card (a very rough approximation of the log_2(n^2)) to get the probability that you reuse a number down to a manageable level, check if you’ve reused a number (which is basically free once you’ve sorted), and then repeat the whole process if you reused a number. Or you could have a lazily calculated infinite precision random number per card and use more like 6 bits per card on expectation. Other than using more (and annoyingly variable) memory, this may well be faster than a properly unbiased Fisher-Yates. Or you could assign a few bits per card, sort, and then recurse on each group of cards that sorted into the same bucket. In summary, there are lots of genuinely unbiased solutions (assuming a perfect binary RNG), and they all boil down to something roughly equivalent to rejection sampling.
pmarreck 1y ago
With all due respect, I don't think you understand. The 128 bits are just to sort the 52 cards into a random-enough order, and they have sufficient entropy and space for that. We're not interested in sorting all possible decks, just all possible cards (52) into 1 unique randomized deck. The more bits we assign to these, the more any error or bias in the source goes to nil. (In contrast, consider the use of only 4 bits.) Since everyone's bashing my use of ChatGPT, I don't think ChatGPT5 would have made that categorical error.
- oneshtein 1y ago
  2^128*52 is 6656 bits, or 30x more than 2^226, so it will work IF those bits are independent. If CSPRNG is used, such as AES128, it will use 2^128 seed, which is not enough to cover all 2^226 permutations. If PRNG sequence is reused to generate more shuffles, then the next shuffle can be predicted from the previous one. CSPRNG AES256 with 2^256 random seed is safe. CSPRNG AES128 with 2^128 (or less) random seed is not safe.
  - tripletao 1y ago
    > If PRNG sequence is reused to generate more shuffles, then the next shuffle can be predicted from the previous one. That's theoretically true by a counting argument, but for a CSPRNG the only way to compute that next shuffle costs about as much computationally as brute force. 128 bits is enough to make that infeasible, though 256 may be preferable for the usual abundance of caution. The number of permutations doesn't matter here, since an attack becomes computationally infeasible before it becomes counting infeasible. It's also possible for a practical attack to exist even when the output can't be predicted exactly, since statistical information is still valuable.

> Turns out that an even easier way is just to assign 128 bits of randomness 52! is roughly 2^226. You cannot address all 2^226 positions with a 2^128 address generated from 2^64 seed.

rcxdude 1y ago

it's 128 bits per card. That's vastly more than 226 bits.

amluto 1y ago
You could use something like 12 bits of randomness per card (a very rough approximation of the log_2(n^2)) to get the probability that you reuse a number down to a manageable level, check if you’ve reused a number (which is basically free once you’ve sorted), and then repeat the whole process if you reused a number. Or you could have a lazily calculated infinite precision random number per card and use more like 6 bits per card on expectation. Other than using more (and annoyingly variable) memory, this may well be faster than a properly unbiased Fisher-Yates. Or you could assign a few bits per card, sort, and then recurse on each group of cards that sorted into the same bucket. In summary, there are lots of genuinely unbiased solutions (assuming a perfect binary RNG), and they all boil down to something roughly equivalent to rejection sampling.

pmarreck 1y ago

With all due respect, I don't think you understand. The 128 bits are just to sort the 52 cards into a random-enough order, and they have sufficient entropy and space for that. We're not interested in sorting all possible decks, just all possible cards (52) into 1 unique randomized deck. The more bits we assign to these, the more any error or bias in the source goes to nil. (In contrast, consider the use of only 4 bits.) Since everyone's bashing my use of ChatGPT, I don't think ChatGPT5 would have made that categorical error.

oneshtein 1y ago
2^128*52 is 6656 bits, or 30x more than 2^226, so it will work IF those bits are independent. If CSPRNG is used, such as AES128, it will use 2^128 seed, which is not enough to cover all 2^226 permutations. If PRNG sequence is reused to generate more shuffles, then the next shuffle can be predicted from the previous one. CSPRNG AES256 with 2^256 random seed is safe. CSPRNG AES128 with 2^128 (or less) random seed is not safe.
- tripletao 1y ago
  > If PRNG sequence is reused to generate more shuffles, then the next shuffle can be predicted from the previous one. That's theoretically true by a counting argument, but for a CSPRNG the only way to compute that next shuffle costs about as much computationally as brute force. 128 bits is enough to make that infeasible, though 256 may be preferable for the usual abundance of caution. The number of permutations doesn't matter here, since an attack becomes computationally infeasible before it becomes counting infeasible. It's also possible for a practical attack to exist even when the output can't be predicted exactly, since statistical information is still valuable.