3

我正在考虑一种算法来解决ax = 1 mod p与 p 素数的一致性。我正在考虑使用费马定理。既然我知道

a ^ (p-1) = 1 mod p

然后

a ^ (p-1) = a * (a ^ (p-2))

这意味着这a ^ (p-2) mod p就是解决方案。不幸的是，这个解决方案虽然在数学上是正确的，但对计算机来说并不好，因为对于大素数我必须这样做a ^ (p-2)，这通常是不可计算的。

哪种算法适合计算机科学？

4

3 回答 3

11

因为对于大素数我必须做a ^ (p-2)这通常是不可计算的。

您需要模幂运算，因此通过 IVlad 提到的平方求幂运算 ，您最多只需要大小数的模乘。中间结果以 为界，因此尽管对于大素数不可计算，但通常是。该方法很容易实现：Θ(log p)p-1p^2a^(p-2)(a ^ (p-2)) % p

unsigned long long invert_mod(unsigned long long a, unsigned long long p) {
    unsigned long long ex = p-2, result = 1;
    while (ex > 0) {
        if (ex % 2 == 1) {
            result = (result*a) % p;
        }
        a = (a*a) % p;
        ex /= 2;
    }
    return result;
}

但有一些缺点。(p-1)^2必须在使用的类型中可以表示（如果使用任意精度整数，这不是问题[除了巨大的 p]），否则由于溢出而导致无效结果，并且它始终至少使用log (p-2)/log 2模乘。

如user448810 所建议的扩展欧几里得算法，或等效的连分数法，永远不会产生大于 的中间值p，从而避免所有溢出问题，如果p是可表示的，并且通常需要更少的除法。此外，它不仅计算素数的模逆，还计算任何两个互素数的模逆。

unsigned long long invert_mod(unsigned long long a, unsigned long long p) {
    unsigned long long new = 1, old = 0, q = p, r, h;
    int pos = 0;
    while (a > 0) {
        r = q%a;
        q = q/a;
        h = q*new + old;
        old = new;
        new = h;
        q = a;
        a = r;
        pos = !pos;
    }
    return pos ? old : (p - old);
}

代码稍长，但优化编译器应该将其编译为一个短循环，每次迭代只使用一个除法。

于 2012-12-30T20:10:18.177 回答
7

计算模逆的通常方法是通过扩展欧几里得算法：

function inverse(x, m)
    a, b, u := 0, m, 1
    while x > 0
        q, r := divide(b, x)
        x, a, b, u := b % x, u, x, a - q * u
    if b == 1 return a % m
    error "must be coprime"
于 2012-12-30T18:58:33.657 回答
1

没有理由这对计算机来说不是一个好的算法，你只需要小心实现，我猜这并不是微不足道的，但也不难。

只需通过平方使用取幂，那么它的大小很可能无关紧要p。

a^n = a^(n / 2) * a^(n / 2) for n even
    = a*a^(n - 1) for n odd
于 2012-12-30T18:57:22.440 回答