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

CodePudding user response：

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 verify them, 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 2⁴⁰*3¹⁰ 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.