algorithm - 计算逆模素数表

Question

我知道扩展欧几里德算法是计算单个数模素数 p 的乘法逆元的理想方法。

但是如果我想创建一个数组A，其中A[x] 是x 的倒数怎么办？有没有比单独计算每个元素的倒数更快的方法来计算这样的数组？

我直觉上希望有一条捷径，因为你有很多身份，比如

A[x*y % p] = A[x]*A[y] % p

但是我想不出获取整个数组 A 的通用方法。

Answer 1

将逆运算减半的简单方法是使用

inverse(p - k) = p - inverse(k)

并使用扩展欧几里得算法仅填充数组的前半部分，并通过对称性填充剩余的一半。

我不确定以下是否会更快，它需要更少的计算，但对数组的访问模式更差，所以它很可能更慢:

int A[p] = {0};
A[1] = 1;
for(int k = 2; k < p; ++k) {
    if (A[k] == 0) {
        // haven't found the inverse yet
        inv = inverse(k,p); // extended Euclidean algorithm or Fermat's theorem
        int m = k, i = inv;
        while(m != 1) {
            A[m] = i;
            m = (m*k) % p;
            i = (i*inv) % p;
        }
    }
}

每次您遇到一个您还不知道其逆的值时，您都会迭代地计算由该值生成的整个子群的逆，每个元素仅使用两次模乘法(除了初始逆)。您应该很快就会用整个单位组对 p 取模生成一个生成器。