0

I would like to shuffle a relatively long array (length ~400). While I am not a cryptography expert, I understand that using a random number generator with a period of less than 400! will limit the space of the possible permutations that can be generated.

I am trying to use Python's random.SystemRandom number generator class, which, in Windows, uses CryptGenRandom as its RNG.

Does anyone smarter than me know what the period of this number generator is? Will it be possible for this implementation to reach the entire space of possible permutations?

Peter O.
  • 32,158
  • 14
  • 82
  • 96
c-wilson
  • 395
  • 3
  • 11
  • 3
    *"I would like to shuffle a relatively long array"* Then why not just use [`random.shuffle`](https://docs.python.org/3/library/random.html#random.shuffle)? Also, a list of 400 elements is not very large at all in most programming contexts, especially relating to RNGs. – Cory Kramer Nov 05 '14 at 17:32
  • 1
    See also: http://stackoverflow.com/questions/25616756 – Peter O. Nov 05 '14 at 17:39
  • You can use same sub arrays with different seeds. The Seeds you can generate in first stage with time or three id or some think else. – Denis Kohl Nov 05 '14 at 17:42

1 Answers1

0

You are almost correct: you need a generator not with a period of 400!, but with an internal state of more than log2(400!) bits (which will also have a period larger than 400!, but the latter condition is not sufficient). So you need at least 361 bytes of internal state. CryptGenRandom doesn't qualify, but it ought to be sufficient to generate 361 or more bytes with which to seed a better generator.

I think Marsaglia has versions of MWC with 1024 and 4096 bytes of state.

Lee Daniel Crocker
  • 12,927
  • 3
  • 29
  • 55
  • Python's `random` module uses a Mersenne Twister generator routine with a state space of 19937 bits. This is seeded from the os `CryptGenRandom` entropy source on import of the module. So for less than 2080 elements this should be ok. – c-wilson Nov 05 '14 at 19:01
  • I'm not fond of Mersenne twister, but it would work. You would still need to make sure you seed it with at least 361 bytes from CryptGenRandom. – Lee Daniel Crocker Nov 05 '14 at 19:28