求 a,b,n 使得 (a^b)%n=x

Question

假设我为 x 选择了一个介于 0 和 2147483647 之间的值。 (Int32.MaxValue) 我想弄清楚如何找到 a,b,n 的值，以便 (a^b)%n=x 我已经知道我可以使用 ModPow 来验证这些值，但我不知道如何找到合适的 a、b 和 n。

#include <iostream>

/// Calculate (a^b)%n
/// \param a The base
/// \param b The exponent
/// \param n The modulo
/// \return (a^b)%n
int ModPow(int a, int b, int n) {
    long long x = 1, y = a;
    while (b > 0) {
        if (b % 2 == 1) {
            x = (x * y) % n; // multiplying with base
        }
        y = (y * y) % n; // squaring the base
        b /= 2;
    }
    return x % n;
}

int main() {

    int x = 1337;

    // How to find a,b,n so that (a^b)%n=x
    int a = ?;
    int b = ?;
    int n = ?;

    if(x == ModPow(a,b,n))
        printf("ok");

    return 0;
}

Answer 1

int n = 2147483647
int a = ModPow(x, 9241, n);
int b = 464773;

n = 2³¹ − 1 是质数。所以由于 Fermat's little theorem, xⁿ mod n = x 和 x^{n − 1} mod n = 1（除非 x = 0）所以 x ^{2 n − 1} mod n = x，也是。 2∆n − 1 = 9241 × 464773。所以 (x⁹²⁴¹ mod n)⁴⁶⁴⁷⁷³ mod n = x。请注意，您需要 x < n 才能正常工作； x = 2147483647 如果 n 也是 31 位（即有符号）整数，则无法工作。

我花了一些时间才到这里；很长一段时间以来，我一直在用 Carmichael numbers and the Carmichael function before I reached this easy solution. See edit history 搞乱这个答案以获取详细信息。

Answer 2

modulus operator:

Yields the remainder given by the following expression, where e1 is the first operand and e2 is the second: e1 – (e1 / e2) * e2

因此无论x的最大值是多少，n都必须更大。由于您使用 n 作为 int 进行验证，并且您正在指定范围：0 和 numeric_limits<int>::max()，因此必须一个独占范围，并且 n 成为 int 唯一可能的值是：numeric_limits<int>::max().

用n强制我们的等式有效地变成：a^b = x.
_{我们需要在这里检查 x 不是 1，如果它是 b = 0 和 a 可以是我们合法范围内的任何值，因此我们可以任意选择 a = 2。但是除了这个：}

我们的要求是：

1 < a < x 并且 a 是一个 int
1 < b < x 并且 b 是一个 int

给定 x，我们可以搜索 a 和 b 的组合，如下所示：

auto a = 0.0;
auto b = 1;

if(x == 1) {
    a = 2.0;
    b = 0;
} else {
    while((a = pow(x, 1.0 / ++b)) > 2.0) {
        double dummy;

        if(modf(a, &dummy) == 0.0) {
            break;
        }
    }
}

此时，如果a >= 2.0 那么问题就有了有效解。现在你可能很清楚，pow 是一个非常昂贵的函数，所以对于较大的 x 值，这可能需要很长时间才能执行，我个人建议找一个 a 和 b 对于存在这样一对的每个数字，并将它们存储在 map 中并对其进行查找。
无论如何，这是工作代码的演示：

Live Example

求 a,b,n 使得 (a^b)%n=x

Find a,b,n so that (a^b)%n=x

c++

math

modular-arithmetic