mod,prime -> inverse possible

Question

I was wondering if one can do the following:

We have:

• X is a product of N-primes, thus I assume unique.
• C is a constant. We can assure that C is a number that is part of the N-primes or not. Whichever will work best.
• X mod C = Z

We have Z and C and we know that X was a product of N-primes, where N is restricted lets say first 100 primes.

Is there anyway we can get back X?

Answer 1

There are infinite primes (and thus infinite products of N primes), but only C possible values of X mod C. Thus, with overwhelming probability, there will be infinite valid X which satisfy X mod C = Z.

So, if you are looking to determine which of those was your original X, then no, that can't be done.

Answer 2

Im not sure if I understand your question correctly, but if you are given Z and C and you want to calculate X.

If X mod C = Z, then this means that for some natural number q it holds that qC+Z = X, since q is unknown, it is in general impossible to calculate X exactly, however, there is an infinite set of numbers satisfying this equation. This is also not strange. Assume you have some X' which could be the solution, then also X'' = X'+C is a solution equally valid.

Whether or not C and X are coprime (i.e. they (dont) have common prime factors) is not relevant, if I'm not mistaking. However, it makes your solution set a bit smaller, because if X and C have common prime factors say p1,p2,...pn, than each valid solution should also be divisible by p1*p2*...*pn.

Answer 3

We'll need some more info to figure this out for you. For instance, if you mean that X is the product of the first N primes, N <= 100, then brute force search will work for you.

If you mean X the product of some subset of the first 100 primes, then it is harder. You are essentially asking if you can tell whether X is smooth or not given X mod Z. If you could do that, you'd probably be able to improve the best known integer factoring algorithms, as they depend on detecting smooth numbers of various forms.

Of course, if you can choose C big enough so X mod C = X, then it is easy.

See http://en.m.wikipedia.org/wiki/Smooth_number for a discussion of smooth numbers.

Answer 4

No. Here is a counter-example:

Suppose X = 105 ( = 3x5x7 ).

Take C = 13 so that X mod C = Z = 1.

However X = 118 ( = 2x59 ) also gives Z = 1 with C = 13.

Answer 5

I don't think so. Because C is not part of X, you are losing information when you do the X mod C operation. Further, mod only returns part of an operation and requires div to get the other portion of the result.

Example: (3*5) % 7 = 1. Because you lost information, I don't see any way to get back to 15 from 1 and 7 without the div portion directly. You'd have to start adding up 7s and adding the remainder and comparing to simulate the missing div portion of the equation.

Answer 6

Your question is rather hard to understand, but maybe you want to read about the Chinese Remainder Theorem.