News for hackers. Stuff that matters.
Re:Kolmogorov Complexity - A Primer by strictfp on Tuesday April 24, 2012 @02:04AM (#3882663)
True. What you say must imply that no PRNG-generated sequence has a particularly high K complexity (> len(PRNG)). What still interests me in this scenario is that a true random source can still generate the same sequence as a PRNG. In that case the complexity of the string becomes small. So for a given true random source you can still get strings with low K complexity. Does this affect cryptography in any way?
Re:Kolmogorov Complexity - A Primer by ajuc on Tuesday April 24, 2012 @10:41AM (#3884132)
No, because cryptography just wants to ensure that given all past bits of generator output you can't predict future bit with probability different than 0.5.

And besides, overwhelming majority of strings are random, once you got to strings long enough. Probabilty that random generator will make not Kolmogorov random string is 0.