4 ms·
A psuedorandom generator G(x) can expand n random bits to n+1 psuedorandom bits that still "look random" to any efficient program that sees them. The existence
by benkuykendall 10y ago
A psuedorandom generator G(x) can expand n random bits to n+1 psuedorandom bits that still "look random" to any efficient program that sees them. The existence of such a G that is efficiently computable is hard to prove (at least as hard as P!=NP) but there are many reasonable functions we theorize to have this property.
So with original entropy x, evaluate G(x) => x', c. Output the random bits c and repeat with x = x'. The sequence of c is psuedorandom.
k=128 is the key length of the generator. We define an efficient program to be one that runs in some time polynomial in k. How big of a k you need is based on how powerful computers are at present.