获得大数 modulo 的有效方法（例如，找到 100 mod x =1 的 x）

Question

Alice 有一个整数 x0，她不想让 Bob 知道。 Bob 知道一个非常大的整数 y，也知道 y mod x0 = 1。所以现在Bob可以解方程y mod x = 1得到不同的x看哪个是正确的（Bob可以验证得到的x的正确性）。 Bob很难得到x0吗？他有什么有效的方法吗？我能想到的一种方法是如下尝试和错误，但我想它效率低下，因此很难得到真实的 x0。谢谢！

示例：Bob 想要 x 100 mod x = 1。可能 x 是 3, 9, 11, 33, 99。 Bob 可以验证该值。假设验证很快。爱丽丝的真实价值是 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

Answer 1

解决这个问题的有效方法是使用有效的整数分解算法：分解 N，选择 y=N+1，然后实现 verify(x)，只有当 x 是 [=24 时才报告 True =] N 的因子（这很容易），那么恢复 x0 的算法将找到 N 的 non-trivial 因子。因此不太可能有非常有效的算法来执行此操作。

但它也可以反过来工作：我们只需要生成 y-1 和 verify 它们的除数，而不是所有可能的数字，然后对 y-1 进行因式分解，然后从这些因数中生成除数在许多情况下比 brute-force 更有效。尽管分解整数很困难^{[需要证明]}，但我们有比 brute-force 更好的算法来做到这一点，尤其是当数字包含小因子或重复因子时。

例如，因式分解 2⁴⁰*3¹⁰ 很容易，然后列出除数很容易而且没有太多其中很多（451 个除数），而 brute-force 方法将花费不合理的时间。一般来说，我们至少可以轻松分解任何 64 位数字。

获得大数 modulo 的有效方法（例如，找到 100 mod x =1 的 x）

Efficient way to get modulo for large number (e.g., find x for 100 mod x =1)

encryption

algorithm

complexity-theory

time-complexity

modulo