# Hiding small numbers in a huge number?

1. Dec 16, 2006

### Ben Huke

Dear number theorists and enthusiasts,

Following is a math-computing problem. If you are interested and want to be paid for solving it, please contact me (benhuke@gmail.com).

Suppose we have a set of n positive 32-bit integers: X = {x1, x2, … x_n}

Find a function f1 such that with T = f1(x1, x2, … x_n), it’s computationally infeasible to decompose T back to x_i's. That is, the time it takes to find the original component numbers will increase exponentially with T. However, also find a function f2 such that if r = f2(T, x) = 0 then we can conclude, with as high a probability (p) as possible, that x is in X.

For a rough example, we can have:

f1: T = x1 * x2 * … * x_n (In this case, with n > 20, is it computationally infeasible to decompose T back to x_i's ?)

f2: r = T mod x

Further requirements: The solution must have a higher p and have f2 more efficient (i.e. requiring less computation) than those in the example.

Sincerely thanks,

Ben

2. Dec 16, 2006

### Hurkyl

Staff Emeritus
I don't think your conditions can be satisfied.

If it takes as long as ten microseconds to compute f2(T, x), one could brute force exhaust through all possible values for x in half a day.

(And my tests indicate that, on my computer, it takes under 3 microseconds to compute the f2 you propose)

3. Dec 16, 2006

### CRGreathouse

No matter what you do, brute force will give all the solutions in 2^32 ~= 4 billion times the time it takes to calculate the f2. Cryptographically speaking, this isn't very strong -- even if you take a tenth of a second generating the number, it would take a cluster of 500 computers just 10 days to cycle through all the possibilities. If there's a faster way to crack it it takes less effort.

Now if you used 64-bit integers the problem becomes much more interesting. Taking 1ms to encode, it would take a million-computer cluster 600 years to cycle through the space. That's more secure by far.

For the latter problem, multiplying the numbers might work. Multiplying and taking a large mod (greatly increasing the work needed for f2, depending on how large you choose the modulus) could be workable.

4. Dec 16, 2006

### Ben Huke

Thanks a lot for your replies.

But if we increase the size of x_i to 64-bit, that will decrease p, right? How to increase p?

5. Dec 17, 2006

### CRGreathouse

It need not. If you're not taking a modulus, and you choose all the x_i to be distinct primes, then p = 1.