On Sunday, 17 November 2013 at 13:07:40 UTC, Timon Gehr wrote:
On 11/17/2013 02:07 AM, Ivan Kazmenko wrote:
The random pick fails in the following sense: if we seed the
RNG,
construct a killer case, and then start with the same seed, we
get
Theta(n^2) behavior reproduced.
Hence, in no sense. This does not perform independent uniform
random picks.
Not at all. There is a number of situations where you want your
program to use RNG, but it is also important for the result to be
reproducible. In such cases, you typically store the RNG seed
for re-use.
Of course there are also many cases where you don't need
reproducibility guarantees, and there, the attack is useless.
Ivan Kazmenko.
