逆元 令加法逆元(-W) 对每一个W∈zn,存在一个z,使得W+z=0modn,则 z即为加法逆元W 令乘法逆元(w-1) ,使得WXZ=1modp。Z即为乘法逆元W 若P为素数,对每个W∈Z,W与p互素,存 一个z 用W以Z中的所有数模p,余数将以不同次序涵盖Z中的所 有数,其中必有一个为1。这个数就是w的乘法逆元,W1 模数不是素数时,某些但非全部整数存在一个乘法逆 元。如果gcd(a,n)=1,则能在Z中找到b,使得a×b=1 modn。b即为乘法逆元a-1 密码学导论一中国科学技术大学 15逆元 ❖加法逆元(-w) ▪ 对每一个w∈Zn，存在一个z，使得w+z≡0 mod n，则 z即为加法逆元-w ❖乘法逆元(w-1) ▪ 若p为素数，对每一个w∈Zp，w与p互素，存在一个z ，使得w×z≡1 mod p。z即为乘法逆元w-1 • 用w乘以Zp中的所有数模p，余数将以不同次序涵盖Zp中的所 有数，其中必有一个为1。这个数就是w的乘法逆元，w-1 ▪ 模数不是素数时，某些但非全部整数存在一个乘法逆 元。如果gcd(a, n)=1, 则能在Zn中找到b，使得a×b≡1 mod n。b即为乘法逆元a -1 密码学导论--中国科学技术大学 15