有效获取大型模型的方法（例如，找到100 mod x = 1的x）
爱丽丝有一个整数x0她不希望鲍勃知道。鲍勃知道一个非常大的整数y，并且也知道y mod x0 = 1。因此，现在鲍勃可以求解方程y mod x = 1获得不同的x查看哪个是正确的（Bob可以验证所获得的x <的正确性/代码>）。 Bob难以获得X0吗？他有没有有效的方法？我能想到的一种方法是在下面尝试和错误，但我想这是低效的，因此很难获得真实的x0。谢谢你！
示例：鲍勃想获得x 100 mod x = 1。可能的X是3，9，11，33，99。鲍勃可以验证值。假设验证很快。爱丽丝拥有的真实值是33。获得此33有多困难？
for i in range(2, y):
if (y-1)%i == 0:
x = (y-1)/i
verify(x) // assume that verification is fast
if verification succeeds:
break
else:
continue
else:
continue
Alice has a integer x0 which she doesn't want Bob to know. Bob knows a very large integer y and also knows that y mod x0 = 1. So now Bob can solve the equation y mod x = 1 to get different x to see which one is correct (Bob can verify the correctness of the obtained x). Is it difficult for Bob to get x0? Are there any efficient way for him? One way I can think of is try and error as below but I guess it's low-efficient and hence is difficult to get real x0. Thank you!
Example: Bob wants to get x for 100 mod x = 1. Possible x are 3, 9, 11, 33, 99. Bob can verify the value. Assume the verification is fast. The true value that Alice has is 33. How difficult it is to get this 33?
for i in range(2, y):
if (y-1)%i == 0:
x = (y-1)/i
verify(x) // assume that verification is fast
if verification succeeds:
break
else:
continue
else:
continue
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
解决这一点的有效方法将暗示有效的整数分解算法：要n，选择y = n+1，并实现
verify（x），以便仅当x是非 - n的琐碎因子（很容易），然后恢复X0的算法会发现n的非平凡因子。因此，这样做的不可能有非常有效的算法。但这也相反：我们只需要生成y-1和
验证的除数，而不是所有可能的数字，然后考虑Y-1，然后从这些因素中生成除数许多情况比蛮力更有效。即使整数很难 [需要证明] ，我们还是有算法要比蛮力更好，尤其是当数字包含小因素或重复因素时。例如，分解2 40 *3 10 很容易，然后列出除数很容易，并且没有太多（451个除数），而野蛮 - 强制方法将花费不合理的时间。通常，我们至少可以轻松地考虑任何64位数字。
An efficient way to solve this would imply an efficient integer factorization algorithm: to factor N, choose y=N+1, and implement
verify(x)such that it reports True only if x is a non-trivial factor of N (which is easy), then the algorithm to recover x0 will find a non-trivial factor of N. So it is unlikely that there will be a very efficient algorithm to do this.But it also works the other way around: we need only generate the divisors of y-1 and
verifythem, not all possible numbers, and factoring y-1 and then generating the divisors from the factors is in many cases more efficient than brute-force. Even though factoring integers is difficult[proof needed], we have algorithms to do it that are better than brute-force, especially if the number contains small factors or repeated factors.For example, factoring 240*310 is easy, and then listing the divisors is easy and there aren't too many of them (451 divisors), while a brute-force approach would take an unreasonable amount of time. In general we can easily factor any 64-bit number at least.