代码之家 › 专栏 › 技术社区 › Kyu96

找到a,b,n以便(a^b)%n=x

modular-arithmetic math c++

-2

Kyu96 · 技术社区 · 6 年前

假设我为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;
}

2 回复 | 直到 6 年前

1

2

MvG 6 年前

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

氮 = 2 ^三十一 –1是质数。因此,由于 Fermat's little theorem , X ^氮国防部 n = X 和 X ^{n

一} 国防部 n = 1(除非 X = 0) X ^{二

氮

一} 国防部 n = X 也是。2埃 n 1=9241_464773。所以( X ^{九千二百四十一} 国防部 n ) ^{四十六万四千七百七十三} 国防部氮 = X 。注意你需要 X &; n 为了让这起作用; X =2147483647无法工作,如果氮也是31位(即有符号)整数。

我花了一段时间才来到这里;很长一段时间我一直在胡思乱想这个答案 Carmichael numbers 以及 Carmichael function 在我找到这个简单的解决办法之前。见 edit history 详情。

2

1

Jonathan Mee 6 年前

这个 modulus operator :

产生以下表达式给出的余数,其中 E1 是第一个操作数,并且 E2 是第二个: e1(e1/e2)*e2

因此无论 x 是, n 必须更大。因为你在验证 n 作为一个 int 你要指定的范围是: 0 和 numeric_limits<int>::max() 那个必须是一个独家系列,并且 氮 成为一个 int 唯一可能的价值是: 数值限制<int>::max() .

用 氮 强迫我们的等式有效地变成: a ^b = X .
_{我们需要检查一下

X

不是

1

,如果是

乙

= 0

和

一

可以是我们合法范围内的任何东西,所以我们可以任意选择

一

= 2

. 但是,尽管如此:}

我们的要求是:

1 & lt; 一 &; X 和 一 是一个 int
1 & lt; 乙 &; X 和 乙 是一个 int

鉴于 X ,我们可以搜索 一 和 乙 其适用范围如下:

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;
        }
    }
}

在这一点上,如果 一 gt=2 那么这个问题就有了一个有效的解决方案。现在你可能已经很清楚了, pow 是一个非常昂贵的函数,所以对于较大的值,这可能需要很长的时间来执行。 X ,我个人建议 一 和 乙 对于这样的一对存在的每个数字,并将它们存储在一个 map 然后查一下。
无论如何,这是工作代码的演示:

Live Example