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

This looks like homework or school/college assignment. Google Answers
Researchers do not answer those.

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.

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.

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.

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.

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.

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.