Hiding small numbers in a huge number?

[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.



Please give my your opinion about this problem (e.g., how difficult is it? is it possibly solvable?).

Sincerely thanks,

Ben

 

[Hurkyl]

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)

 

[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.

 

[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?

 

[CRGreathouse]

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

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