Register to reply 
Hiding small numbers in a huge number? 
Share this thread: 
#1
Dec1606, 09:16 AM

P: 2

Dear number theorists and enthusiasts,
Following is a mathcomputing 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 32bit integers: X = {x1, x2, x_n} Find a function f1 such that with T = f1(x1, x2, x_n), its 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 


#2
Dec1606, 09:40 AM

Emeritus
Sci Advisor
PF Gold
P: 16,091

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
Dec1606, 12:58 PM

Sci Advisor
HW Helper
P: 3,684

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 64bit integers the problem becomes much more interesting. Taking 1ms to encode, it would take a millioncomputer 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
Dec1606, 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 64bit, that will decrease p, right? How to increase p? 


#5
Dec1706, 02:56 AM

Sci Advisor
HW Helper
P: 3,684




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 