

Subject:
Incorporating numbers?
Category: Science > Math Asked by: arintelga List Price: $200.00 
Posted:
25 Nov 2006 08:42 PST
Expires: 25 Dec 2006 08:42 PST Question ID: 785462 
Suppose we have some positive integers: x1, x2, ? xn. We can integate them into a composit number by calculating T = x1 * x2 * ? * xn. If T is a huge number, it?s computationlly infeasible to decompose it exactly back to the original component numbers: x1, x2, ?, xn. However, given any number x, we can calculate r = T mod x (r is the remainder of an integer division of T by x). If r is 0, there?s a chance (p) that x is one of the original component numbers. Question: Find other arithmetic/logic operations which can replace the multiplication & mod in the scenario above with higher efficiency (higher p & less computational processing than mod).  
 


There is no answer at this time. 

Subject:
Re: Incorporating numbers?
From: politicalguruga on 25 Nov 2006 11:35 PST 
This looks like homework or school/college assignment. Google Answers Researchers do not answer those. 
Subject:
Re: Incorporating numbers?
From: arintelga on 25 Nov 2006 13:27 PST 
This is not a homework or school/college assignment. It's from my current security project for my own company. In fact, it's not a trivial problem. Remember the requirement that it be computationally infeasible for one to decompose T back to the original component numbers if T is large enough. 
Subject:
This doesn't look serious
From: machlearnga on 27 Nov 2006 17:42 PST 
I'm afraid that you may not understand the question. It can indeed be a serious security challenge. However, a properly stated problem would identify the following:  whether the x_i are prime or composite  If the x_i are prime, then your initial statement about factorization is, in most cases, incorrect.  whether the x_i are unique or appear with multiplicity  whether there are assumptions about the x_i, e.g. of the form 2^k +/ 1, or of any arbitrary size  whether a relationship is sought between asymptotic p and numerical operations  the size (in bits, for instance) of the x_i and T. Frankly speaking, a single mod calculation doesn't tell you much. I think that you may be unaware of, say, the Euclidean algorithm. If your company is serious about this, they should consult a number theorist. If it is for a security product, more serious investigators than you and Google Answers should be involved. 
Subject:
More suggestions for your homework
From: machlearnga on 27 Nov 2006 18:19 PST 
I thought about it some more, and now I'm convinced you're working on homework. It is a clever enough problem from your professor. First, you didn't rule out that the T might be even or have other amusing properties. For instance: if the last digit is 2: boom, one of the factors is 2. You can keep doing this. There are nice tricks for testing if it is divisible by 2, 4, 8, whatever. Just do division. Faster than mod. Sum the digits: if the sum is divisible by 3, T is divisible by 3. Last digit a 5? You know what happens... Other tricks exist for 7, 11, and so on. Just learn about mod 10, mod 100, mod 1000, etc., arithmetic and you may identify some of the other tricks. Do I get $200 for solving your homework? I'll take just $25, since you still have to put your name on it. 
Subject:
Re: Incorporating numbers?
From: arintelga on 28 Nov 2006 14:12 PST 
To MachLearn: I would pay you $5 for each good number theorist's contact information (up to 3). Clarification: 1. x_i is an arbitrary 32bit number. 2. x_i may appear with multiplicity. 3. There may be from 10 to 20 component numbers, which means T can be hundred of bits long. 4. The properties of T are dependent on the method you choose to incorporate the x_i numbers together. In the example I used multiplication. You may have a better way to do it such that you can find a different checking method more efficient than mod. I don't understand your question about the relationship. How would you apply the Euclidean algorithm for this problem? Suppose x_i is prime and T is HUGE. Would you show me how it is computationally feasible to decompose T into component numbers? Thanks P.S. By the way, I graduated last May. So, again, this is not a homework. 
Subject:
Re: Incorporating numbers?
From: mathisfunga on 28 Nov 2006 18:02 PST 
Not sure I really get the problem but would using prime factorization then combinatorics to make all possible combinations of n factors work, say after you have all possible 1000 combinations that 725 have x_i as a factor then x_i has a 72.5% chance of being one of the original n numbers. Long runtime but fairly accurate I would think. 
Subject:
Re: Incorporating numbers?
From: arintelga on 28 Nov 2006 20:09 PST 
The question is not to calculate p or find x_i. The question is to find other operations that can replace the multiplication & mod operations in the example such that you will have a method to conclude, with a higher accuracy p, whether an x is one of the original component numbers. This checking method should require as less computation than the mod operation as possible. Also, the new operation that you use to integrate the component numbers into T must guarantee that it's computationally infeasible to decompose T back to the original components when T is large. That is, the time it takes to decompose T will increase exponentially with the size of T. 
If you feel that you have found inappropriate content, please let us know by emailing us at answerssupport@google.com with the question ID listed above. Thank you. 
Search Google Answers for 
Google Home  Answers FAQ  Terms of Service  Privacy Policy 