乘法逆元及其求法
如果ax≡1 (mod p),且gcd(a,p)=1（a與p互質(zhì)），則稱a關(guān)于模p的乘法逆元為x。下文中，x都表示乘法逆元。 2.費(fèi)馬小定理
假如a是一個(gè)整數(shù)，p是一個(gè)質(zhì)數(shù)，那么是p的倍數(shù)，可以表示為
我們都知道模就是余數(shù)，比如12%5=12-5*2=2，18%4=18-4*4=2。（/是程序運(yùn)算中的除）
那么ax≡1 (mod p)即ax-yp=1.把y寫成+的形式就是ax+py=1，為方便理解下面我們把p寫成b就是ax+by=1。就表示x是a的模b乘法逆元，y是b的模a乘法逆元。然后就可以用擴(kuò)展歐幾里得求了。
求a/b=x(mod M）
只要M是一個(gè)素?cái)?shù),而且b不是M的倍數(shù),就可以用一個(gè)逆元整數(shù)b1,通過 a/b=a*b1 (mod M)，只能來以乘換除。
費(fèi)馬小定理:對于素?cái)?shù) M 任意不是 M 的倍數(shù)的 b，都有：b ^ (M-1) = 1 (mod M)
于是可以拆成：b*b^(M-2)=1(mod M)
于是:a/b=a/b*(b * b ^ (M-2))=a*(b ^ (M-2)) (mod M)
求a/b=x(mod M)
用擴(kuò)展歐幾里德算法算出b1,然后計(jì)算a*b1(mod M)
exgcd(b,M,x,y); ? b1=x;
?
當(dāng)p是個(gè)質(zhì)數(shù)的時(shí)候有
inv(a) = (p - p / a) * inv(p % a) % p
?
證明：
設(shè)x = p % a,y = p / a
于是有 x + y * a = p
(x + y * a) % p = 0
移項(xiàng)得 x % p = (-y) * a % p
x * inv(a) % p = (-y) % p
inv(a) = (p - y) * inv(x) % p
于是 inv(a) = (p - p / a) * inv(p % a) % p
然后一直遞歸到1為止，因?yàn)?的逆元就是1
總結(jié)
- 上一篇： Three.js数据结构、导入导出(.t
- 下一篇： QCC304x系列开发教程（实战篇) 之