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

每次遇到一个您还不知道其逆的值时，您就迭代地计算由该值生成的整个子组的逆，每个元素仅使用两个模乘（除了初始求逆）。您应该相对较快地击中整个单位组的生成器 modulo p。

Answer 2

对于 pa 素数，元素 {1, 2, 3, ..., (p-1)} 形成一个循环群。也就是说，存在一个数（实际上很多）x，使得 {x^0, x^1, x^2, ..., x^(p-2)} 是集合。找到x的倒数后，称其为y，只需将y乘以适当的幂即可得到对应的倒数，y^k就是x^k的倒数。你怎么找到这样的x？选择一个随机元素并将其提高到 (p-1)/2 的幂。该数字将是 1 或 -1 (p-1)。如果它是-1，你有你的发电机。将元素提高到幂应该使用“平方求幂”来完成。

Answer 3

以下代码来源于 mod 函数的定义：

public long[] InverseTable(long n, long p)
{
    long[] inverse = new long[n+1];
    inverse[1] = 1;
    for (long i = 2; i <= n; i++)
        inverse[i] = p - (inverse[p % i] * (p / i) % p);
    return inverse;
}