因为对于大的素数，我必须要做的事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模块化乘法。

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

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