复杂取模运算简化

$a^n\left(\mod m\right)$

• STEP1: 分解$m$ $m=m_1\cdots m_k$

• STEP2: 欧拉定理 $$$$

• STEP3: 利用中国剩余定理求解 $a^n\equiv b\left(\mod m\right)$

应用

• RSA解密加速

• 残差数字系统