mod，prime ->逆可能
我想知道是否可以执行以下操作：
我们有：
X是N-primes 的乘积，因此我假设是唯一的。C是一个常数。我们可以确定C是一个数字，它是否是N素数的一部分。哪个效果最好。X mod C = Z
我们有 Z 和 C 并且我们知道 X 是 的产物N-素数，其中 N 受到限制，假设前 100 个素数。
无论如何我们可以找回X吗？
I was wondering if one can do the following:
We have:
Xis a product ofN-primes, thus I assume unique.Cis a constant. We can assure thatCis a number that is part of theN-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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
素数有无限个（因此
N个素数的乘积也有无限个），但X mod C的可能值只有C个。因此，以压倒性的概率，将有无限个有效的X满足X mod C = Z。因此，如果您想确定其中哪一个是您的原始
X，那么不，这是不可能的。There are infinite primes (and thus infinite products of
Nprimes), but onlyCpossible values ofX mod C. Thus, with overwhelming probability, there will be infinite validXwhich satisfyX mod C = Z.So, if you are looking to determine which of those was your original
X, then no, that can't be done.我不确定我是否正确理解你的问题，但如果给你 Z 和 C 并且你想计算 X。
如果 X mod C = Z，那么这意味着对于某些自然数 q 它保持 qC+Z = X，由于 q 未知，通常不可能精确计算 X，但是，有无限组数字满足该方程。这也并不奇怪。假设您有一些 X' 可能是解决方案，那么 X'' = X'+C 也是一个同样有效的解决方案。
如果我没有记错的话，C 和 X 是否互质（即它们（不）具有共同的质因数）并不相关。然而，它使您的解决方案集稍微小一些，因为如果 X 和 C 具有共同的质因数，例如 p1,p2,...pn，那么每个有效解决方案也应该可以被 p1*p2*...*pn 整除。
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.
我们需要更多信息来为您解决这个问题。例如，如果您的意思是 X 是前 N 个素数的乘积，N <= 100，那么暴力搜索将适合您。
如果你的意思是 X 是前 100 个素数的某个子集的乘积，那么它就更难了。你本质上是在问你是否可以判断 X 是否平滑或不给定 X mod Z。如果你能做到这一点，你可能能够改进最著名的整数分解算法，因为它们依赖于检测各种形式的平滑数。
当然，如果你可以选择足够大的C，使得X mod C = X，那么这很容易。
请参阅 http://en.m.wikipedia.org/wiki/Smooth_number 了解光滑数的讨论。
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.
你的问题很难理解，但也许你想阅读中国剩余定理。
Your question is rather hard to understand, but maybe you want to read about the Chinese Remainder Theorem.
不，这是一个反例：
假设 X = 105 ( = 3x5x7 )。
取 C = 13，使得 X mod C = Z = 1。
然而，X = 118 ( = 2x59 ) 也给出 Z = 1，且 C = 13。
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.
我不这么认为。由于 C 不是 X 的一部分，因此当您执行 X mod C 运算时，您会丢失信息。此外，mod 仅返回操作的一部分，需要 div 才能获取结果的其他部分。
示例：(3*5) % 7 = 1。因为您丢失了信息，所以我看不到任何方法可以在没有 div 部分的情况下直接从 1 和 7 返回 15。您必须开始将 7 相加，然后添加余数并进行比较，以模拟方程中缺少的 div 部分。
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.