这个系列是MIT Open Courseware Mathematics for Computer Science^1的记录
同余
a与b模n同余, 记作$a \equiv b(mod \space n)$, 如同字面上的意思, 它表示$rem(a, n) = rem(b, n)$. 等价地, 它还表示$n|(a-b)$.
考察$a = kn + rem(a, n)$, 发现$n|rem(a, n)-a$, 那么就有：
- $a \equiv rem(a, n)(mod \space n)$
同余关系是等价关系, 因此自反, 传递且对称. 除此之外, 以下性质值得注意:
- $a \equiv b (mod \space n)\implies a+c \equiv b+c(mod \space n)$
- $a \equiv b (mod \space n)\implies ac \equiv bc(mod \space n)$
- $a \equiv b (mod \space n) \land c \equiv d (mod \space n) \implies a+b \equiv c+d(mod \space n)$
- $a \equiv b (mod \space n) \land c \equiv d (mod \space n) \implies ac \equiv bd(mod \space n)$
这里只是证明一下4, 而3的证明类似, 其余的比较明显.
$a \equiv b (mod \space n) \implies ac \equiv bc(mod \space n)$
$c \equiv d (mod \space n) \implies bc \equiv bd(mod \space n)$
$由传递性, ac \equiv bd(mod \space n)$
事实上, 在我瞎折腾的过程中, 发现由传递性还可以得到另一个有趣的结果. 如果p, q互质, 那么有$tp \equiv 1(mod \space q)$, 此时如果有另一个数r满足$(r \equiv p(mod \space q)$的话, 由于$(tr \equiv tp(mod \space q)$, 故$tr \equiv 1(mod \space q)$, 也就是r, q互质.
也就是说. 如果p, q互质, 且r与p模q同余, 则, r与q也互质.
这里只有$+-\times$, 但是却没有$/$. 考察$ka \equiv kb(mod \space n)$, 什么情况下能够把k从两边消掉呢.
之前说过$a \equiv b(mod \space n) \iff n|(a-b)$, 那么也有$ka \equiv kb(mod \space n) \iff n|k(a-b)$.
也就是说只要能保证$n|k(a-b) \implies n|(a-b)$就能保证$ka \equiv kb(mod \space n) \implies a \equiv b(mod \space n)$.
那么有一点是肯定的, 那就是n和k如果互质(relatively prime)的话, 那么必然满足上述条件, 当然也存在其它满足的情况, 有兴趣的可以深究, 但是现在我们只要知道以下事实就够了.
- $如果a, b互质, 有ka \equiv kb(mod \space n) \implies a \equiv b(mod \space n)$
前一篇文章^2曾经说过, gcd(a, b)实际上是a和b的最小线性组合. 而a, b互质又可以写成gcd(a, b)=1, 亦即$\exists t, a, 使得ta+sb=1$, 也就是说$ta \equiv 1(mod \space b)$.
我们定义t为a在mod b条件下的乘法逆元. 如此一来, 我们就有:
- $如果a, n互质, 则存在a在mod \space n条件下的乘法逆元$
欧拉函数
介绍完同余, 来看看欧拉函数.
欧拉函数$\phi(n)$定义为小于n且于n互质的数的个数.
对于质数p, 显然有$\phi(p)=p-1$.
然后再来考察一堆互质的数p, q, 令r=pq. 定义比n小且与n互质的数的集合为Zn.
由p, q互质可知, 对于任意的一个$k \in Zr$, 都存在$ap + bq=k(mod \space r)$, 而且在mod r的语境下可以将a调整在(0, q), b调整到(0, p). 显然满足上述区间的a, b唯一(考虑$(a+mq)p+(b-mq-tq)p=k$), 而且a跟q互质, b跟p互质(否则与$k \in Zr$矛盾), 亦即$a \in Zq \land b \in Zp$. 于是有一个从$Zr$到$Zq \times Zp$的双射, 于是$\phi(pq) = \phi(p) \times \phi(q)$. 特别地, 如果p, q都是质数, 则$\phi(pq) = (p-1)(q-1)$. (事实上, 还可以用中国余剩定理反过来建立映射, 也可以证明).
由于合数可以唯一地表示为质数幂的乘积(算术基本定理), 一个自然的想法是研究质数幂的计算方法, 这样就可以构造出任意欧拉函数的计算方法了.
考察质数的幂$p^k$, 由于比p小且与p不互质的数有$(p, 2p, \space \cdots \space, (p^{k-1}-1)p)$共$p^{k-1}$个, 于是$\phi(p^{k})=p^k-p^{k-1}$.
那么就得到任何数的欧拉函数计算方法:
- $\phi(n)=n\times\prod\limits_{p_i \in n的质因数} (1- \frac{1}{p_i})$
(其实推了那么多对于RSA并没有什么卵用, 只是推着玩玩, 真正有用的只有”如果p, q都是质数, 则$\phi(pq) = (p-1)(q-1)$”这一句)
费马小定理
介绍欧拉函数之后之后, 就可以开始介绍费马小定理了. 费马小定理是这样说的:
$gcd(p, n)=1 \implies p^{\phi(n)} \equiv 1(mod \space n)$
这看起来就有点吓人了, 但其实有了前面的铺垫, 证明起来还是很简单的. 首先来证明一个小结论.
设比n小而且与n互质的数为$A={n_1, n_2, \space\cdots\space, n_r}$, 其中$r=\phi(n)$. 再构造一个数列$B={rem(pn_1, n), rem(pn_2, n), \space\cdots\space, rem(pn_r, n)}$. 显然有$(rem(pn_1, n) < n-1) \land (gcd(rem(pn_1, n), n)=1) \land (B中元素两两不同)$.
综合这三个条件可以得出: B是A的一个全排列.
那么就有：
$n_1 \cdot n_2 \cdots n_r$
$=rem(pn_1, n)\cdot rem(pn_2, n) \cdots rem(pn_r, n)$
$\equiv pn_1 \cdot \cdots \cdot pn_r$
$=p^{\phi(n)}\cdot n_1 \cdot n_2 \cdots n_r(mod \space n)$
$消去, 得1 \equiv p^{\phi(n)}(mod\space n)$
RSA
那么终于来到了最后一步, 也就是传说中的RSA. 我们先来给出RSA的加密解密步骤, 然后再来证明其正确性.
步骤是抄来的, 懒得翻译了.
- Generate two distinct primes, p and q. Since they can be used to
generate the secret key, they must be kept hidden.
- Let n = pq.
- Select an integer e such that $gcd(ed, (p-1)(q-1)) = 1$.
The public key is the pair (e, n). This should be distributed widely.
- Compute d such that $de \equiv 1(mod\space (p-1)(q-1)$. This can be done using the Pulverizer.
The secret key is the pair (d, n). This should be kept hidden!
- Encoding: Given a message m, the sender first checks that gcd(m, n) = 1 The
sender then encrypts message m to produce m’ using the public key:
$m’ = rem(m^e, n)$
- Decoding: The receiver decrypts message m’ back to message m using the secretkey:
$m = rem((m’)^d, n)$
因为m比n小, 所以要证明这一堆东西的正确性, 只需要证明$(m’)^d \equiv m(mod \space n)$.
有了前面的铺垫, 证明变得及其简单：
$m’ = rem(m^e, n) \implies m’ \equiv m^e(mod\space n) \implies (m’)^d \equiv m^{ed}(mod\space n)$
$de \equiv 1(mod\space (p-1)(q-1) \implies de=1+r(p-1)(q-1)$
$所以, (m’)^d \equiv m\times m^{r(p-1)(q-1)}(mod\space n)$
$\implies (m’)^d \equiv m(mod \space n)$
