复杂取模运算简化

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

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

• STEP2: 欧拉定理 $$\left\{ \begin{array}{**lr**} a^{n_1}\equiv 1\left(\mod m_1\right) &\\ \vdots &\\ a^{n_k}\equiv 1\left(\mod m_k\right) \end{array} \right. \Longrightarrow \left\{ \begin{array}{**lr**} a^{n}\equiv b_1\left(\mod m_1\right) &\\ \vdots &\\ a^{n}\equiv b_k\left(\mod m_k\right) \end{array} \right.$$

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

应用

• RSA解密加速

• 残差数字系统