algorithm - 计算 $a ^ {^nC_r}$ % 素数

Question

我已将我的问题上传为屏幕截图。

Answer 1

费马小定理

x^p mod p = x mod p     or     x^(p-1) mod p = 1  (if p does not divide x)

当 p 不除 x:

1. 将m除以(p-1)得到:s = (m mod p-1);无需计算商数
2. 注意 m = (p-1)q + s 和 x^(p-1) = 1 mod p。所以，
   • x^m = x^((p-1)q)x^s = (1^q)(x^s) mod p = x^(m mod p-1)

但是，剩下的问题是如何计算

choose(n,r) = n(n-1)...(n-r+1)/(r(r-1)...1) mod p-1

附录

对上述问题的进一步思考使我们考虑以下问题。我们有三个整数:

c = choose(n,r)
m = n(n-1)...(n-r+1)
f = factorial(r)
q = p-1

满足

c = m/f,                                 eq 1

我们必须回答的问题是计算c mod q是否有效

(c mod q) = (m mod q)/(f mod q)          eq 2

对吧？因为这将使我们能够将 choose(n,r) 的计算减少为两个系列的模乘加一个除法(一种简单而高效的算法)。

现在，eq 1可以改写为

 c*f = m

这使我们能够将 mod q 应用于两侧:

 (c mod q)(f mod q) = (m mod q)          eq 3

因为已知 mod 与乘积(和和)交换，这正是我们将用来计算上述模乘系列的属性。

并且由于eq 3中涉及的树数量是整数，我们可以将两边除以(f mod q)得到eq 2。我的回答现在完成了。

附录 2

我说过我的回答现在已经完成了。不完全的。当 f mod q = 0 时仍然存在问题，在这种情况下我们不能像上面那样划分 eq 3。这种情况需要特殊处理，并将导致更复杂的算法。

一个值得尝试的想法是分解 q，即 p-1 作为素数的乘积，并逐个考虑这些素数及其指数。取其中一个，说t^e。我们知道 t^e 必须除以阶乘 f。因此，它也必须划分 eq 3 的右侧。因此，我们必须在 n, n-1, n-2, ..., n-r+1 中查看足够多的因子，这些因子可以被 t 整除，直到我们穷尽e 除以 t。然后我们需要用相应的 t 次方的商替换这些因数。对 q=p-1 内的所有素数重复此过程后，我们将在左侧得到 f/q，在右侧得到新的因子列表。这将是我们的新版本 eq 3。当然，新的 f (=f/q) 可能会再次被 q 整除。因此，我们必须重复相同的过程，直到 f mod q 不再是 0。到那时，我们将能够划分并获得 c mod q 的值。