计算 32 位 int 的阶乘(mod prime)比 C 中的 O(n) 快

Question

可能的重复项：
快速计算n！mod m 哪里 m 是素数？

让：

int k = 99999989;

k是一个质数。

给定一些（32位）int x，我们想要计算x阶乘模k。

一种方法如下：

int factmk(int x)
{
    long long t = 1;
    for (long long i = 2; i <= x; i++)
    {
         t *= i;
         t %= k;
    }
    return (int)t;
};

这需要 O（x） 时间和 O（1） 空间。

有没有一种渐近更快的方法在小于或等于 O（logx） 空间的直线 C 中实现factmk？ 如果是，那是什么？ 如果没有，请提供草图证明。

Answer 1

这不是一个笼统的答案，但作为一个特例，如果x = k-1，你可以使用威尔逊定理

(x)! = -1 mod k

或

(p-1)! = -1 mod p