计算$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)

我们可以使用它来减少计算x^m (m任意)的操作数量，当p不除以x时

1. 将m除以(p-1)并得到：s = (m mod p-1)；不需要计算m = (p-1)q + s和x^(p-1) = 1 mod p的quotient
2. Note。所以，
   • 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中涉及的树量是整数，因此我们可以用到达eq 2的(f mod q)除以两边。我的答案现在已经完成了。

附录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的值。

Answer 2

https://en.m.wikipedia.org/wiki/Fermat%27s_little_theorem表示当p不除以x时，(x^y) mod = x^(y (p-1)) mod。