c++ - 模乘反函数不适用于负数

Question

我有下面的函数来计算给定模数 p 的数 n 的模乘逆。

int modInverse(int n, int p) {
    n %= p;
    for(int x = 1; x < p; x++) {
        if((n*x) % p == 1) return x;
    }
}

如果 n 是正数，它工作正常，但如果 n 是负数，它总是给出 0。我该如何解决？

x mod n的乘法逆:x^-1 mod n，是必须乘以x得到1 mod n的数例如3^-1 mod 7 = 5，因为 3 * 5 = 1 mod 7

Answer 1

示例代码:

int modulo(int n, int p)
{
int r = n%p;
    if(((p > 0) && (r < 0)) || ((p < 0) && (r > 0)))
        r += p;
    return r;
}

int modInverse(int n, int p) {
    n = modulo(n, p);
    for(int x = 1; x < p; x++) {
        if(modulo(n*x, p) == 1) return x;
    }
    return 0;
}

int main(void)
{
int r;
    r = modInverse(-25, 7);
    return 0;
}

如果你想要商和余数:

void divmod(int n, int p, int &q, int &r)
{
    q = n/p;
    r = n%p;
    if(((p > 0) && (r < 0)) || ((p < 0) && (r > 0))){
        q -= 1;
        r += p;
    }
}