My both attempts at PRNGs resulted in rather short cycles -- ones that were easily compressed several-times-fold by GZIP and similar algorithms. Thus I consider them to have been trivially reducible.

Yes, a well designed PRNG algorithm and implementation can be quite simple, but it is quite hard to design them well. It takes either non-trivial math, or non-trivial amount of iterative improvements.