加法逆元和乘法逆元 加法逆元(-W 0对每一个W∈Zn,存在一个z,使得 W+z≡0modn,则z即为加法逆元-W 乘法逆元(Wl 0对每一个W∈Z,存在一个z,使得w×z≡1modp, p为素数,W与p互素,则z即为乘法逆元W 因为w与p互素,如果用w乘以乙中的所有数模p,得到 的余数将以不同次序涵盖Z中的所有数,那么至少有 个余数的值为1。因此,在乙中的某个数与w相乘模p 的余数为1,这个数就是W的莱法逆元w 在模数不是素数时,某些但非全部整数存在一个乘法逆 元(如上页的模8运算)。如果gcd(a,n)=1,则能在zn 中找到b,使得axb≡ 1 mod n,则b即为乘法逆元a-1, 因为a与n互素。7 网 mfy@ustc.edu.cn 现代密码学理论与实践 16/55mfy@ustc.edu.cn 现代密码学理论与实践 16/55  加法逆元(-w) ◦ 对每一个w∈Zn，存在一个z，使得 w+z≡0 mod n，则z即为加法逆元-w  乘法逆元(w-1) ◦ 对每一个w∈Zp，存在一个z，使得w×z≡1 mod p， p为素数， w与p互素，则z即为乘法逆元w-1 ◦ 因为w与p互素，如果用w乘以Zp中的所有数模p，得到 的余数将以不同次序涵盖Zp中的所有数，那么至少有一 个余数的值为1。因此，在Zp中的某个数与w相乘模p 的余数为1, 这个数就是w的乘法逆元, w-1 ◦ 在模数不是素数时，某些但非全部整数存在一个乘法逆 元（如上页的模8运算）。如果gcd(a, n)=1, 则能在Zn 中找到b，使得axb ≡1 mod n，则b即为乘法逆元a -1 , 因为a与n互素