Hiding small numbers in a huge number?

  • Thread starter Ben Huke
  • Start date
  • Tags
    Numbers
In summary: If you are taking a modulus, you can get a lot of values of p.In summary, the conversation is about a math-computing problem involving a set of positive 32-bit integers. The goal is to find two functions, f1 and f2, where f1 makes it computationally infeasible to decompose T back to the original numbers in the set, and f2 can determine with a high probability if a given number is in the set. The solution must have a higher p and be more efficient than the example given. The potential solutions involve using larger integers or choosing distinct primes. The difficulty and feasibility of the problem are also discussed.
  • #1
Ben Huke
2
0
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
 
Physics news on Phys.org
  • #2
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
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
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
Ben Huke said:
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.
 

What is the concept of hiding small numbers in a huge number?

The concept of hiding small numbers in a huge number is a mathematical technique known as steganography. It involves embedding a small number within a larger number in a way that is not immediately apparent to an observer.

Why would someone want to hide a small number in a huge number?

Hiding small numbers in a huge number can be used for various purposes, including encryption, data compression, and secret communication. It can also be used in puzzles and games for entertainment purposes.

How does one go about hiding a small number in a huge number?

There are various methods for hiding small numbers in a huge number, such as using prime factorization, modular arithmetic, and bitwise operations. The specific technique used will depend on the specific application and the level of security needed.

What are the potential drawbacks of hiding small numbers in a huge number?

One potential drawback is that the hidden number may be vulnerable to being discovered through statistical analysis or other mathematical techniques. Additionally, the process of hiding and retrieving the hidden number may be computationally intensive, leading to slower performance in certain applications.

Are there any real-world applications of hiding small numbers in a huge number?

Yes, steganography is used in various real-world applications, such as digital watermarking, copyright protection, and secure communication. It is also used in some financial transactions and cybersecurity techniques.

Similar threads

Replies
13
Views
899
Replies
16
Views
2K
  • Topology and Analysis
Replies
11
Views
1K
  • General Math
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
10
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Differential Equations
Replies
3
Views
2K
Replies
4
Views
287
  • Math Proof Training and Practice
2
Replies
61
Views
7K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
917
Back
Top