The complexity cannot be over 10,000,000 if that simple program generated it. That is the precise definition of complexity.

I don’t understand what you mean by reducibility to random strings, randomness has precisely nothing to do with complexity, even if they do tend to go together.