初等數(shù)論--同余方程--同余方程運算：模逆運算，模指數(shù)運算

博主是初學(xué)初等數(shù)論（整除+同余+原根），本意是想整理一些較難理解的定理、算法，加深記憶也方便日后查找；如果有錯，歡迎指正。
我整理成一個系列：初等數(shù)論，方便檢索。

同余方程：$ax\equiv b(modm)$

• 模逆運算：若$(a,m)=1,$那么由上一章信息安全數(shù)學(xué)基礎(chǔ)–同余方程–同余方程的解證明的“同余方程$ax+b\equiv 0(modm)$的解個數(shù)為$(a,m)$”得，同余方程$ax\equiv b(modm)$的解個數(shù)為$(a,m)$。
  $ax\equiv b\to x\equiv a^{?1}b(modm)$
  進(jìn)行模逆運算，求$a^{?1}(modm)$,即求方程$ax\equiv 1(modm)$的解,$\to ax=1+km\to ax?km=1?ax+my=1$，運用歐幾里得算法/輾轉(zhuǎn)相除法 求$x$。

• 模指數(shù)運算：若$(a,m)=1,$那么由歐拉定理知$a^{\phi (m)}\equiv 1(modm)$,那么$ax\equiv b\to x\equiv a^{?1}b\to x\equiv a^{\phi (m)?1}b(modm)$
  進(jìn)行模指數(shù)運算，求$a^n(modm)$
  $$\begin{gathered} n=n_k?2^k+n_{k?1}?2^{k?1}+\dots \dots +n_1?2^1+n_0?2^0 \\ {a}^n=a^{n_k?2^k+n_{k?1}?2^{k?1}+\dots \dots +n_1?2^1+n_0?2^0} \\ =(a^{n_k}{)}^2?a^{n_{k?1}}{)}^2\dots \dots a^{n_1}{)}^2?a^{n_0} \end{gathered}$$

總結(jié)

以上是生活随笔為你收集整理的初等数论--同余方程--同余方程运算：模逆运算，模指数运算的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。