数论:有效模指数

Question

如果：

开始{ &= }k} a\cdot b\cdot c\ cdot c\ k_m &= k \bmod m \ bmod m\ a_m &= a \bmod m\ b_m &= b \bmod m\ c_m &= c\bmod m\ \end{align}

那么$B^{k_m} \bmod N$总是等价于：

$$\left(左(B^{a_m} \bmod )^{b_m} \bmod N\右)^ {c_m} \bmod N$

如果不是，什么是反例？

Answer 1

如果不是，什么是反例？

反例：

$a = 2，b= 2，c= 2，m= 3，N= 5，B= 2$

在本例中，$k = 8$和$k_m = 2$。

我们有$B^{k_m} bmod N= 4$，但是$(B^{a_m}bmod N)^{b_m} \bmod N)^{c_m} \bmod N= 1$

另一方面，如果$N$是素数，并且$m = N-1$，那么它总是正确的。

Answer 2

根据欧拉定理，对于$m:= \phi(N)$，$\phi$是欧拉函数 (在$N$是素数的特例中，有$\phi(N)=N-1$，如果$N$是两个不同素数$p$和$q$的乘积，则有$\phi(N)=(p-1)(q-1)$)，如果$B_k$和$N$是相互作用的。通常，在计算模$N$时，可以计算指数模$\phi(N)$，所以

$k_m\equiv k=a\cdot b\cdot c\equiv a_m\cdot b_m\cdot c_m \mod \phi(N)$

因此

$B^k_m\equiv B_m^{a_m\cdot b_m\cdot c_m} =(B_m^{a_m})^{b_m})^{c_m})\mod N$。

如果$m$是一个任意数字(或者$B_k$和$N$有一个除$1以外的公共除数)，则标识通常是假的。