基本介绍

数论中的逆元

基本介绍

设<G,·>是一个幺半群，e是G的单位元，x∈G，若存在x'∈G，使得：

1. x'·x = e，则称x'是x的左逆元。

2. x·x' = e，则称x'是x的右逆元。

3. 若x'既是x的左逆元，又是x的右逆元，则x'称为x的逆元。

注意：

1.G中元素的左逆元和右逆元不一定相等。

2.G中元素不一定都存在逆元。

数论中的逆元

在模运算中，

加法单位元是0，因为(0+a) mod m = a mod m；

乘法单位元是1，因为(1×a) mod m = a mod m

定义 对a∈Zm，存在b∈Zm，使得a+b ≡ 0 (mod m)，则b是a的加法逆元，记b= - a。

定义 对a∈Zm，存在b∈Zm，使得a×b ≡1 (mod m)，则称b为a的乘法逆元。

逆元在密码学中有广泛应用，AES密码体系的字节替代就是运用了逆元。

具体计算逆元时，计算加法逆元的方法是很显然的。而对于乘法逆元：在mod m的操作下（即Zm中），a存在乘法逆元当且仅当a与m互质。不定方程ab+mx=1的任意一组整数解(b,x)，b就是a的乘法逆元。具体计算可以使用扩展欧几里德算法(Extended-GCD)。