RSA算法(三):数论知识(进阶)

原创 小赛艇  2018-06-02 20:16  阅读 565 次

3.4 同余

3.4.1 同余的定义

比如这样的问题:已知6月2日星期六。今年6月哪几天星期六?

显然,2,9,16,23,30号都是星期六,这些数字有个重要的特点,都是除以7的余数为2,我们就称作模7同余,于是给出同余的定义:

若\(a\mod n=b\mod n\),则称a和b模n同余,记为:\(a\equiv b \pmod n\)

3.4.2 同余的性质

另一方面,可以发现2,9,16,23,30这些任意两个数之差都是7的倍数,所以有

同余的等价形式:\(a\equiv b \pmod n \Longleftrightarrow n|a-b \Longleftrightarrow kn=(a-b) (k为整数)\)

例 \(23\equiv 9 \pmod 7, 则23-9=14=2×7\)

由以上等价形式,不难得出以下性质

设\(a\equiv b \pmod n\),\(c\equiv d \pmod n\)

性质(1)\(a+c\equiv b+d \pmod n\)

性质(2)\(ac\equiv bd \pmod n\)

(1)(2)即同余的数同或同以同余的数,仍是同余的。于是可得:

性质(3)\(ka\equiv kb \pmod n (k为整数)\)

性质(4)\(a^k\equiv b^k \pmod n (k为正整数)\)

除了加法乘法外,还有一个"除法",当两个数含有与n互质的因数时,可以消去:

性质(5)若\(mx\equiv my \pmod n, 且(m,n)=1(即m,n互质)\)

则\(x\equiv y \pmod n\)

有了这些性质,我们就可以解决像这样的问题:今天星期六,过\(2004^{2004}\)天之后星期几?

解:
即求\(2004^{2004}\mod 7\)
首先求\(2004÷7=286...2\),即\(2004\equiv 2 \pmod 7\)
由性质(4),\(2004^{2004}\equiv 2^{2004} \pmod 7\)
又\(2^{2004}=8^{668}, 8\equiv 1 \pmod 7\)
所以\(2^{2004}\equiv 8^{668}\equiv 1^{668}\equiv 1 \pmod 7\)
所以\(2004^{2004}\equiv 1\pmod 7\)

所以\(2004^{2004}\)天后星期日,看起来很复杂的题也能很简单地解决了。

3.5 剩余类

上节中提到的2,9,16,23,30这些数都是模7余2,我们可以用一个集合来表示它:[2]。这就是一个剩余类:将与a模n同余的整数构成的集合叫做模n的一个剩余类,记为\([a]\)。

即 \(a\equiv b \pmod n \Longleftrightarrow [a]=[b] \)

显然,模n不同余的两个数一定属于两个不同的剩余类。

由同余的性质不难得到剩余类的性质:

加法:\([a]+[b]=[a+b]\)

乘法:\([a][b]=[ab]\)

为什么要使用"剩余类"这个说法呢?因为要引出逆元的概念:

若\([a][b]=[1]\),则\([b]\)叫做\([a]\)的逆元,\([a]\)可逆。

例 n=7时,\([3][5]=[15]=[1]\),则\([3]\)与\([5]\)互为逆元。

\([a]\)可逆的充分必要条件是\((a,n)=1\),即a与n互质,简单证明见后。

例 n=6时,\([2][3][4]\)都不可逆,\([1],[5]\)可逆,\([1][1]=[1], [5][5]=[25]=[1]\)

那如果给出一个剩余类\([a]\),(a,n)=1,怎么求\([a]\)的逆元呢?

假设\([a]\)的逆元为\([b]\)
则\([a][b]=[ab]=1\)
根据剩余类相等的等价形式有\(ab\equiv 1 \pmod n\)
根据同余的等价形式有\((ab-1)=kn (k为整数)\)
所以\(b=\frac{kn+1}{a}\)
取k使得b为整数即可。

由剩余类逆元的求法可知,如果a与n不互质(假设最大公因数(a,n)=c,则\(a=xc, n=yc\)),代入\((ab-1)=kn\)可化为\(xcb-1=kyc\),即\((xb-ky)c=1\),等式左边为c的倍数,等式右边为1不为c的倍数,等式显然不成立。

3.6 欧拉定理

介绍了同余剩余类这两个重要的概念后,就可以引出数论中重要的定理之一——欧拉定理。

3.6.1 欧拉函数

欧拉函数\(\varphi (n)\)表示1~n中与n互质(即(x,n)=1)的正整数的个数。

例 1~18中,与18互质的数有1,5,7,11,13,17,则\(\varphi (18)=6\)

通过质因数分解求欧拉函数:对于大于1的整数n,如果它的质因数分解式为\(n=p_1^{a_1}p_k^{a_k}...p_k^{a_k}\),则\(\varphi (n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})\)

例 \(18=2×3^2\),则\(\varphi (18)=18×(1-\frac{1}{2})(1-\frac{1}{3})=6\)

这个式子的证明比较复杂,省略。对于质数p,\(\varphi (p)=p×(1-\frac{1}{p})=p-1\)

3.6.2 欧拉定理

设n为正整数,整数a与n互质(即(a,n)=1),则\(a^{\varphi (n)}\equiv 1 \pmod n\)

证明:
设\(\varphi (n)=k\)
这意味着1~n中有k个数与n互质,设这些数为\(b_1, b_2, ..., b_k\)
因为\(b_1, b_2, ..., b_k\)与n的最大公因数为1,a与n的最大公因数也为1,可知\(b_1a, b_2a, ..., b_ka\)与n的最大公因数为1,
即\(b_1a, b_2a, ..., b_ka\)也与n互质。
又因为\(b_1a, b_2a, ..., b_ka\)两两不同余(反证即可)。
所以\(b_1a, b_2a, ..., b_ka\)这些数分属于\([b_1], [b_2], ..., [b_k]\)k个剩余类中(顺序不一定相同),即任取一个\([b_xa]\),有一一对应的\([b_y]=[b_xa]\)。
接下来把这些\([b_1a], [b_2a], ..., [b_ka]\)和\([b_1], [b_2], ..., [b_k]\)用剩余类的乘法相乘:
有\([b_1a][b_2a]...[b_ka]=[b_1][b_2]...[b_k]\)
则\([b_1b_2...b_ka^k]=[b_1b_2...b_k]\)
等价于\(b_1b_2...b_ka^k\equiv b_1b_2...b_k \pmod n\)
由同余的消去性质(5),消去\(b_1b_2...b_k\)可得\(a^k\equiv 1 \pmod n\)

举个例子:

例 \(\varphi (18)=6\),(301,18)=1,则\(301^6\equiv 1 \pmod {18}\)

3.6.3 费马小定理

特别地,当n为质数时,整数a满足(a,n)=1,则\(a^{n-1}\equiv 1 \pmod n\)

这是因为前面已经提到,对于质数n,\(\varphi (n)=n-1\)

例 757是质数,(757,1234)=1,则\(1234^{756}\equiv 1 \pmod {757}\)
例 7是质数,(2004,7)=1,则\(2004^6\equiv 1 \pmod 7\),又因为\(2004=6×334\),所以\(2004^{2004}\equiv (2004^6)^{334}\equiv 1^{334}\equiv 1 \pmod 7\)。这与前面算的相同。

本节介绍了同余剩余类的概念,推导出了重要的定理——欧拉定理。有了这些基本的数论知识,我们就可以理解RSA的算法的原理了。

本文地址:https://xsaiting.com/rsa-3.html
版权声明:本文为原创文章,版权归 小赛艇 所有,转载请保留出处!
喜欢请点赞/打赏/分享这篇文章哦!

发表评论


表情