Hiding small numbers in a huge number?


by Ben Huke
Tags: hiding, number, numbers
Ben Huke
Ben Huke is offline
#1
Dec16-06, 09:16 AM
P: 2
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
Phys.Org News Partner Science news on Phys.org
Simplicity is key to co-operative robots
Chemical vapor deposition used to grow atomic layer materials on top of each other
Earliest ancestor of land herbivores discovered
Hurkyl
Hurkyl is offline
#2
Dec16-06, 09:40 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101
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
CRGreathouse is offline
#3
Dec16-06, 12:58 PM
Sci Advisor
HW Helper
P: 3,680
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
Ben Huke is offline
#4
Dec16-06, 03:31 PM
P: 2

Hiding small numbers in a huge number?


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
CRGreathouse is offline
#5
Dec17-06, 02:56 AM
Sci Advisor
HW Helper
P: 3,680
Quote Quote by Ben Huke View Post
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.


Register to reply

Related Discussions
Number Theory: Fermat Numbers coprime => infinite # primes Calculus & Beyond Homework 3
Every number we know makes up exactly 0% of numbers General Math 28
Unimaginably huge number, No jokes... General Discussion 8
Appoximating a very large number as a small formula General Math 15
Infineti number of prime numbers proof General Math 13