It is known that existence of pseudorandom generators (PRGs) is equivalent to the existence of one-way functions. In turn, the latter is an open problem.
I am curious if someone developed kind of "practical" PRGs, which are weaker than PRGs in terms of computational indistinguishably to uniform random number generators.
I know of some statistical tests for randomness, but is there any rigorous theory on the subject?
The construction and validation of a PRG using one-way functions is the subject of Practical Construction and Analysis of Pseudo-randomness Primitives
A different approach, using chaotic maps, is implemented in Hardware implementation of pseudo-random number generators based on chaotic maps
Cryptographically-secured PRNG's (CSPRNG) output bit sequences that are indistinguishable in polynomial time from "truly random sequences" (defined as having entropy rate 1bit/bit). They typically rely on hard number-theoretic problems (prime factorization, discrete logarithm on elliptic curves, etc.). Well-known examples are the Blum-Blum-Shub and NIST SP 800-90A. They are not the most efficient PRNG in terms of computational complexity per output bit.
That's why we also find plenty of more "practical", lighter and faster PRNGs that do not enjoy polynomial time indistinguishability, such as Linear congruential generator, Permuted congruential generator, Inversive congruential generator, etc. See e.g. List of random number generators.
One of the leading expert in this area was George Marsaglia. He designed the well-known Diehard tests suite for testing PRNGs. There are many other popular tests e.g. Maurer's Universal Test, many security/cryptographic standards such as FIPS_140-2, AIS20 or ISO/IEC 19790 and ISO/IEC 15408 requiring such statistical tests, and even companies specialized in the RNG testing an security certification business.
As a complement to the other answers, if the goal is cryptographic strength [given the context stated by the OP, I assume it is] in a PRNG that will be used in practice, then the randomness testing methods can be used to rule out generators as being weak, but obviously cannot rigorously demonstrate randomness.
In terms of the CSPRNGs, such as Blum-Blum-Shub (BBS), which is the most well-known example, care must be taken that the extraction rate of "cryptographically strong bits" is not too high compared to the state space of the BBS iteration. The theoretical suggestion is if the iteration is $$ x_{k+1}=x_k^2 \pmod n,\quad n=pq $$ where $p$ and $q$ are large primes, one should at most take $O(\log \log n)$ least significant bits of $x_k$ and output them as pseudorandom bits.
This approach is full of pitfalls, however. Firstly, the specification is asymptotic, so what's a reasonable constant to use in front of the $O(\cdot)$ expression? Vanstone and Menezes in an Indocrypt paper suggested not to use more than 1 bit, i.e., just the least significant bit.
More seriously [see the first answer to this question in crypto stackexchange for details] it turns out that the security reduction in BBS is so inefficient that maybe it should not be used at all in practice.
Suppose you use BBS with a 768-bit modulus. You've read that 768 bits is enough to make factoring infeasible, so this sounds peachy. You've read that it is safe to extract O(lg n) bits in each iteration; here n = 768, and lg n = 9.58, so you decide to extract 9 bits in each iteration. You use it to generate a pseudorandom stream of 107 bits (about 1MB of pseudorandom data). How much security do you get? Answer: the security proof guarantees security against any adversary that uses at most $2^{-264}$ steps of computation. Yes, this is an utterly ridiculous and useless statement! To put it in plain English, the security proof guarantees absolutely nothing useful at all.
On the other hand if one wanted security against an attack of complexity approximately $2^{100}$ steps (reasonable since $2^{128}$ brute force complexity is standard these days) one would have to choose $n$ of about 6800 bits. This is now more feasible since RSA moduli of 4096 bits are now common.
Notwithstanding this, it is amazing how inefficient the security proof reduction in BBS is. One can demonstrate that breaking BBS and is $1054 n^3$ times faster than factoring the BBS modulus $n.$
So practical CSPRNG security is a moving target, very dependent on algorithmic developments.
