我想知道是否可以执行以下操作：
我们有：
X是N-primes 的乘积，因此我假设是唯一的。C是一个常数。我们可以保证这C是一个是否属于N-primes 的数字。无论哪种方式效果最好。X mod C = Z
我们有Z并且C我们知道这X是N-primes 的乘积，其中N受限的地方可以说是前 100 个素数。
无论如何我们可以回来X吗？
6 回答
2
我不这么认为。因为 C 不是 X 的一部分，所以在执行 X mod C 操作时会丢失信息。此外，mod 只返回操作的一部分，并且需要 div 来获取结果的另一部分。
示例：(3*5) % 7 = 1。因为您丢失了信息，所以我看不出有任何方法可以在没有 div 部分的情况下直接从 1 和 7 回到 15。您必须开始将 7s 相加并添加余数并进行比较以模拟等式中缺少的 div 部分。
于 2010-05-19T20:19:21.427 回答
2
不，这是一个反例：
假设 X = 105 ( = 3x5x7 )。
取 C = 13，使得 X mod C = Z = 1。
然而 X = 118 ( = 2x59 ) 也给出 Z = 1 和 C = 13。
于 2010-05-19T20:27:27.683 回答
0
您的问题很难理解，但也许您想阅读有关中国剩余定理的信息。
于 2010-05-19T20:18:44.140 回答
0
我们需要更多信息来为您解决这个问题。例如，如果您的意思是 X 是前 N 个素数的乘积，N <= 100，那么蛮力搜索将为您工作。
如果您的意思是 X 是前 100 个素数的某个子集的乘积，那就更难了。您本质上是在询问您是否可以判断 X 是否平滑给定 X mod Z。如果您能做到这一点，您可能能够改进最知名的整数分解算法，因为它们依赖于检测各种形式的平滑数.
当然，如果你可以选择足够大的 C 使得 X mod C = X，那就很容易了。
有关平滑数字的讨论，请参见http://en.m.wikipedia.org/wiki/Smooth_number。
于 2010-05-19T20:44:55.420 回答
0
我不确定我是否正确理解了您的问题，但是如果给您 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 整除。
于 2010-05-19T20:48:47.563 回答
0
有无限的素数（因此有无限的N素数乘积），但只有C的可能值X mod C。X因此，以压倒性的概率，将存在满足的无限有效X mod C = Z。
因此，如果您要确定其中哪一个是您的原件X，那么不，那是做不到的。
于 2010-05-20T21:19:48.613 回答