View Question
 Question
 Subject: Incorporating numbers? Category: Science > Math Asked by: arintel-ga 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).``` Clarification of Question by arintel-ga on 25 Nov 2006 13:34 PST `Also, prove that your solution has higher efficiency.` Request for Question Clarification by mathtalk-ga on 12 Dec 2006 09:00 PST ```I'd like to understand the purpose for which one would "replace the multiplication & mod" in your scenario. Let me relate what you've said, and I think you'll see where I'm confused. Starting with an input set(?) of positive integers, they can be combined (with loss of information, except for restricted circumstances such as all primes) by taking their product T. Factoring large numbers T is thought to be a hard problem, so in the absence of further information, recovering the original set of multiplicands might be said to be "computationally infeasible" even if one restricts attention to the case of two large prime factors. You include in your scenario the circumstance that one knows a number x for which the remainder of T mod x turns out to be zero, and you define probability p that then x is in the original input (conditioned on x dividing T). Note that if we were considering only positive prime inputs, the probability p = 1. Your Question is then about replacing multiplication & mod (division) with "higher efficiency" alternatives. What I'm confused by is the definition of this as "higher p & less computational processing", especially given your assertion in the Comments below that we should remember "the requirement that it be computationally infeasible for one to decompose T back to the original component numbers if T is large enough." I'm not sure that "higher p" is what your really wanted to say here. I say this because "higher p" appears to argue strongly for a less secure encoding, specifically making it more likely (given some more easily computed information than taking remainders) that at least one of the input integers can be discerned. The point is especially important in that you ask for proof that "your solution has higher efficiency." Bear in mind that assertions about the magnitude of p require assumptions about the distribution of inputs, as for example the restriction of these to prime numbers in the scenario you outlined makes p = 1. regards, mathtalk-ga```
 There is no answer at this time.

 Subject: Re: Incorporating numbers? From: politicalguru-ga 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: arintel-ga 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: machlearn-ga 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: machlearn-ga 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: arintel-ga 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 32-bit 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: mathisfun-ga 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: arintel-ga 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.```