密码学第4章简单数论和有限域基本概念

4.1 整除理论：

b|g 且 b|h 对任意m,n 有 b|(mg+nh)。
2.整除三角理论： a|(b+c),a|b 则 a|c
可以和1构成扩展。
3.传递性：a|b , b|c 则 a|c。

4.2 Euclid算法：

只要证明gcd(a,b)，若b>a且b = am+r。
则有gcd(a,b) = gcd(a,r)。
证明如下：
$令d = gcd(a,b),d|a,d|b$
$d|b -> d|am+r$
$d|a -> d|am$
$由于整除三角,所以d|r$
$可以设d'=gcd(a,r)。然后证明d'|d , d|d' 来证明d=d'$

4.3 模运算：

同余： $\equiv$
同余类的引出。
(1) n|(a-b) 那么 $a \equiv b (mod n)$
这条经常被用来证明同余，因为整除理论里面有强大的（1）和（2），三角理论。

用符号 $Z_n$ 来表示模n的剩余类。
乘法逆元存在性的表征现象。

扩展euclid：
求解这样的： $ax+by = d = gcd(a,b)$ 方程的。
而这样的方程是有扩展性的。
ax+by = k
若上述方程有解，那么d|k。
因为k = ax+by，并且d|a并且d|b 所以d|k。
从而可以设k = qd.只要求解 $ax+by=d$ 的方程的解，若解为(x',y')那么方程 $ax+by=k$ 的解就为(qx',qy')。

从而问题在于求解 $ax+by = d = gcd(a,b)$
算法很简单，只要基于以下两个原理：
我们不影响答案地认为a>b。
那么

b = 0的时候。d = gcd(a,0) = a,从而有解 (x=1,y = 0)。
2.方程 $ax+by = gcd(a,b)$ 和方程 $bx+(a%b)y = gcd(b,a%b)$ 同解。
证明：(x,y) = (x',y') 其中(x,y)为 $ax+by=gcd(a,b)$ 的解，(x',y')为 $bx+(a%b)y=gcd(b,a%b)$ 的解。
因为： $gcd(a,b) = gcd(b,a%b)$
所以： $ax+by=bx'+(a%b)y'=bx'+(a- \lfloor \frac{a}{b} \rfloor)$
$ax$

密码学第4章 简单数论和有限域基本概念

4.1 整除理论：

4.2 Euclid算法：

4.3 模运算：

推荐阅读更多精彩内容

密码学第4章简单数论和有限域基本概念