It it possible to "compress" a list of large numbers using their prime factors?

Question

On a computer I can have integers on arbitrary size thanks to GMP, so it's represented in base 2 in memory.

I'm wondering if it's possible in theory to use less memory if I store only prime factors and their exponent, I think it's worthless for most numbers, but I wonder if it works for a very small minority of numbers with large prime factors.

How can I prove me wrong ?

Answer 1

No, it is not possible. In general, there is no algorithm that compresses every $n$ bit string, or reduces the length of a random string of bits (in expectation).

Your algorithm may compress some numbers but then it will use more memory to store others. If your data is random, there is no benefit in using your compression scheme.

Actually the fact that no such compression scheme exists can be used to prove that there are infinitely many prime numbers — otherwise, if there were only finitely many prime numbers your compression scheme would be very efficient!

There are excellent lecture notes on Kolmogorov Complexity by Alexander Shen that discuss “incompressability”; in particular, Shen writes about your compression algorithm in Section 18.

Answer 2

Something which sort of implies that the answer might be yes in some circumstances (I specialize in precision!) is that solving linear equations with large integer coefficients can be done by solving the system modulo a number of primes (or relatively prime values such as $2^n-1$ for appropriate $n$) and combining the results using the Chinese remainder theorem. You have to have enough moduli so the their product is larger than any of the results.