# Efficient way to represent large(1m digits) numbers beyond entropy encoding

I want to represent numbers that range from 1000 to 1m digits using either 1) large powers or 2) random numbers. So far, I was able to narrow it down to a search problem where you have a large number N, and use a random number generator to find R, such that

N mod R = smallest possible number found from random search

The random numbers have the same number of digits as N, minus 2. The idea is that on the receiving end one could generate the same random number R given the number of iterations it took to generate it, as along as both the generator and receiver share the same random seed.

This approach takes forever...

I would like to find a power, say

89^181484289 + C = N // found power from base_89(N)

But seems like every time I calculate a base by calculating log_base(N), C has the same number of digits as N, or very close. No savings. I thought about using modular arithmetic, where the receiving end gets a formula of the form:

N ≡ M x C + b

Plus some approximation of C, but it still takes forever to compute N in the receiving end. I do not want to use sum of squares, too little savings.

Any thoughts? thanks

• What kind of accuracy do you want? If you want an approximation, just take log base <insert convenient number here> twice – Simply Beautiful Art Mar 19 '17 at 1:09
• No approximations such that the difference between the original number and the approximation has pretty much the same number of digits as N, the original number. Difference in number of digits should be orders of magnitude – Pinhead Mar 19 '17 at 1:15
• Then just take the log twice. $$\log_{10}(\log_{10}(N))$$The result should be between 3 and 6, pretty compact for saving your number in. – Simply Beautiful Art Mar 19 '17 at 1:17
• @SimplyBeautifulArt its not close enough :( – Pinhead Mar 19 '17 at 2:17
• I do not think that this is possible. Random number of such magnitudes will not be "near" a perfect power with a "small" base. – Peter Mar 19 '17 at 12:27