New answers tagged pseudo-random-generators
2
In the average case, you want the circuit to succeed in computing the function for a large portion of all possible inputs. Since a constant function always succeeds for at least half the inputs (the majority of $f$), the interesting case in where you can achieve advantage which is greater than $\frac{1}{2}$.
In the worst case, you want the circuit to succeed ...
2
Intuitively, pseudorandom functions are functions that look random. A linear function $f$ satisfies
$$ f(x+y) = f(x)+f(y) $$
for all $x,y$, which is highly unlikely for a random function. Similarly, an affine function $f$ satisfies
$$ f(x+y) - f(x+z) = f(y) - f(z) $$
for all $x,y,z$, which is highly unlikely for a random function.
1
Theorem 1 in [Nisan Wigderson 1988] implies:
For any function $l\le s(l)\le 2^l$, the following are equivalent:
For some $c>0$, there exists a quick PRG $G: l\to s(l^c)$.
For some $c>0$, there exists a function $f$ in EXPTIME with hardness $s(l^c)$.
Although their definition of (quick) PRG and hardness are slightly different from yours, I think the ...
1
Yes - this is a consequence of the Law of Large Numbers. https://en.wikipedia.org/wiki/Law_of_large_numbers
Yes - it still holds for pseudorandom number generators if they are any good.
Seed each PRNG independently.
0
I produced now a simple overview of most of the known RNG's, with its speed and quality, based on improved dieharder tests.
https://rurban.github.io/dieharder/QUALITY.html
For TestU01 and PractRand results see the linked https://github.com/lemire/testingRNG overview, but yields the same results. You just need to wait days for the same results.
Best and ...
0
If you choose $G$ from the uniform random distribution on $\{0, 1\}^n \to \{0, 1\}^{2^{\epsilon n}}$ without restrictions, then nothing can (correctly) distinguish between the uniform distribution and the output of $G$, because you made it uniformly random by definition. At this point the output of $G$ is no longer pseudo-random, it is random.
Top 50 recent answers are included
