Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

"This is not a property of true randomness." #18

Closed
vigna opened this issue Nov 8, 2019 · 0 comments · Fixed by #23
Closed

"This is not a property of true randomness." #18

vigna opened this issue Nov 8, 2019 · 0 comments · Fixed by #23

Comments

@vigna
Copy link

vigna commented Nov 8, 2019

This is a statement appearing in the book about equidistribution.

This is a very slippery statement. Any property of the full period is not a property of full randomness.

Say, you have a w-bit generator with w-bit output. To be "truly random", every output must be possible. OK, so your generator generates every output.

But now it is necessarily equidistributed: it generates each value exactly once along its period. if it was truly random, after O(sqrt(2^w)) outputs you should find collisions (i.e., duplicate outputs), but you won't because collisions can happen only after 2^w outputs.

You can do the same with any generator with state size kw—just look for blocks of kw bits. They must all appear (it's random, right) but then you won't find collisions at the right time.

In essence, whenever you make a statement about the full period, you can turn it into whatever you want, depending on the viewpoint.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant