Register to reply

Hiding small numbers in a huge number?

by Ben Huke
Tags: hiding, number, numbers
Share this thread:
Ben Huke
#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
NASA team lays plans to observe new worlds
IHEP in China has ambitions for Higgs factory
Spinach could lead to alternative energy more powerful than Popeye
Hurkyl
#2
Dec16-06, 09:40 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,099
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
#3
Dec16-06, 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 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
#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
#5
Dec17-06, 02:56 AM
Sci Advisor
HW Helper
P: 3,684
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