在质数模下找到一个数的逆元

Question

我在考虑一种算法来解决形如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)，这通常是无法计算的。哪种算法适用于计算机科学呢？

- Zagorax

---

你是否知道这篇关于计算整数倒数的论文（http://ipa.ece.illinois.edu/mif/pubs/web-only/Frank-RawMemo12-1999.html）？我相信它对你可能会有用。 - RBarryYoung

Answer 1

因为对于大质数，我需要计算 a ^ (p-2)，通常是无法计算的。

你需要模幂运算，所以使用 平方法 IVlad提到的，你只需要进行 Θ(log p) 模乘运算，数字大小最多为 p-1。中间结果受到 p^2 的限制，因此尽管对于大质数而言 a^(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 模乘法。

扩展欧几里德算法，正如 用户448810建议的，或者等价的连分数方法，从不产生比 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);
}

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

- Daniel Fischer

Answer 2

计算模反元素的正常方法是通过扩展欧几里得算法：

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"

- user448810

---

这很正常吗？谁说的？在科学中，正常意味着什么都没有。这是一个有效的替代方案，但你不能说这是“正常的方式”。 - IVlad

我非常怀疑那些是他的确切话语，但无论如何，这并不意味着它是正确的。这与使用费马定理一样正常。 - IVlad

@IVlad 扩展欧几里得算法是计算模质数的逆元的常规方法。在这里，“常规”指的是任何严肃工作中实际使用的方法，包括用户448810。只需阅读一些关于质数逆元的论文，你就会发现每个人都使用上述算法，因为它比模幂运算更好。 - Bakuriu

@Bakuriu - 嗯，不是的。在正式的论文中，没有人会谈论哪个算法是正常的，哪个不是。他们会根据上下文中的优势选择一个算法而不是另一个。说一个算法是正常的毫无意义。它并不是“比...好得多”，每个算法都有其用途、优点和缺点。 - IVlad

@IVlad 我的意思是这样的：让我们更清晰地重新定义“正常”：如果处理问题P的论文和程序（人类历史上编写的）中有超过51％使用算法A来解决问题P，那么我们说算法A是解决问题P的正常方法。根据这个“正常”的定义，扩展欧几里得算法是求模质数的逆元问题的正常算法。 - Bakuriu

Answer 3

对于计算机来说，这是一个很好的算法，没有任何理由不使用它。但需要注意实现，这可能并不是微不足道的，但也不难。

只需使用平方求幂算法，那么p有多大可能都不会成为问题。

a^n = a^(n / 2) * a^(n / 2) for n even
    = a*a^(n - 1) for n odd

- IVlad

---

我很确定你写错了...a^n = a^(n / 2) for n even 没有任何意义，而且那个链接也没有说到这个。 - nbrooks