本页面已浏览150次

RSA加密是欧拉定理的精妙应用。解密中的关键步骤是求解\(x^E\equiv m\pmod{pq}\)。这是我们第一次接触到高于1阶的多项式同模问题。本章我们继续讨论高阶多项式的同余。

高阶同余

多项式中的一个最基本的定理是代数基本定理（Fundamental Theorem of Algebra）。它告诉我们：

拉格朗日定理：对于\(n\)阶的多项式\(f(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x_1+a_0\)最多有\(n\)个根。

我们在这里不给出证明，但给出对\(p\)求模的对应版本。

定义：我们称\(r\)是多项式\(f(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x_1+a_0\)的根，当且仅当\(f(r)=0\)。

定理6.1：令多项式\(f(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x_1+a_0\)，其中\(n\gt 0, a_n\ne 0, a_i\in\mathbb{Z}\)。那么\(r\)是\(f(x)\)的根当且仅当存在一个阶数为\(n-1\)的整数系数多项式\(g(x)\)，使得\(f(x)=(x-r)g(x)\)。

要证明这个定理，需要引入多项式除法算法：

多项式除法算法：令\(f(x), g(x)\)是首项为1的整数系数多项式，而且\(g(x)\ne 0\)。那么存在唯一的整数系数多项式\(q(x), r(x), deg(r)\lt deg(q)\)或者\(r(x)=0\)使得\(f(x)=g(x)q(x)+r(x)\)。

这个算法的证明和除法算法证明类似，此处从略。

根据多项式除法算法，我们有\(f(x)=(x-r)q(x)+r(x)\)，而且\(deg(r)<1=deg(x-r)\)或者\(r(x)=0\)。这意味着\(r(x)\)是一个常数\(c\in\mathbb{Z}\)。

于是，\(f(r)=(r-r)q(r)+c=c\)。

因此\(r\)是\(f(x)\)的根表明\(f(r)=0\iff c=0\iff f(x)=(x-r)q(x)\)。而\(q(x)\)的阶数必然是\(n-1\)。

本征根

费马小定理告诉我们\(a^{p-1}\equiv 1\pmod{p}\)，但对于有些数\(a\)来说，不需要到幂次\(p-1\)也能得到相同的结果。让我们继续讨论\(ord_p(a)\)的细节。

定理6.4：假定\(p\)是一个素数，而\(ord_p(a)=d\)，那么对于任何自然数\(i\)，若\((i, d)=1\)，那么\(ord_p(a^i)=d\)。

证明：

令\(ord_p(a^i)=l\)。\((a^i)^d=a^{id}=a^{di}=(a^d)^i\equiv 1\pmod{p}\implies l\mid d\)。

又\((i, d)=1\implies ix+dy=1\)。于是：\(a^l=(a^{ix+dy})^l=a^{ixl}a^{dyl}=((a^i)^l)^x(a^d)^{yl}\equiv 1^x1^{yl}=1\pmod{p}\implies d\mid l\)。

所以，\(d=l=ord_p(a^j)\)。QED。

这个定理告诉我们，所有那些对\(p\)求模同秩的数字。下一个定理告诉我们，有多少互相不同余的自然数可以对\(p\)求模同秩。

定理6.5：对于素数\(p\)和一个自然数\(d\)，最多有\(\phi(n)\)个对\(p\)求模互不同余的整数对\(p\)的秩是\(d\)。

证明：

费马小定理告诉我们，如果\(x^n\equiv 1\pmod{p}\)有解，那么\(n\mid (p-1)\)。如果\(n\nmid(p-1)\)，那么定理显然是成立的。所以我们以下只证明\(n\mid(p-1)\)的情况。

假定\(n\mid(p-1)\)，而\(ord_p(a)=n\)。根据定理6.4，\(ord_p(a^j)=n\)对于所有\(1\le j\le n\)，且\((j, n)=1\)的情形都成立。这样的\(j\)正好有\(\phi(n)\)个，但有些这样的幂可能对\(p\)求模得到相同的结果，所以最多有\(\phi(n)\)个这样的数对\(p\)的秩是\(d\)。

定义：令\(p\)为一个素数。一个整数\(g\)，如果\(ord_p(g)=p-1\)，那么\(g\)被称为对\(p\)求模的本征根。

定理6.6：令\(p\)为一个素数，而\(g\)是对\(p\)求模的一个本征根。那么集合\(\{0, g, g^2, g^3, ..., g^{p-1}\}\)构成对\(p\)的完全余数集。

证明：

这个定理很像定理4.8：

定理4.8：令\(a, n\in\mathbb{N}, (a, n)=1, k=ord_n(a)\)，那么\(a^1, a^2, ..., a^k\)两两一定与\(n\)不同模，也就是\(a_i\not\equiv a_j\pmod{n}, i\ne j\)。

练习6.7：对于小于20的素数\(p\)，找出一个它的本征根，以及本征根的各次幂给出小于\(p\)的各个自然数。

练习：

首先，强调一下：求本征根是很繁琐的工作。从原则上说，你需要从\([2, n-1]\)这里找一个数字，每个数字进行\([2, n-2]\)（思考一下为什么是这个区间？）的幂运算才行。这个计算很繁琐。但有一些快捷的方式。以下会进行说明。

\(p=2\implies p-1=1\)，但2的任何次幂都是偶数，对2求模都是0。但是，\(1^1\equiv 1\pmod{2}\)，所以也可以说1是对2求模的本征根。这是个特例，不过还是请记住。

\(p=3\implies p-1=2\)。我们要找到一个数字\(g\)，使得\(ord_3(g)=2\iff g^{3-1}\equiv 1\pmod{3}\)。

我们考虑2：\(2^2\equiv 1\pmod{3}\)，正确。

这么看来，3的一个本征根是2。

5：我们要考虑的是\(g^{5-1}\equiv 1\pmod{5}\)。很幸运，2就是这么一个数字：\(2^4=16\equiv 1\pmod{5}\)。所以2是对5求模的本征根！同时我们注意到：

次方	数值	对5求模
1	2	2
2	4	4
3	8	3
4	16	1

下一个素数是7，我们可以试验2,3,5,6这四个数字，为什么不试验4？因为4=2*2，如果2不是本征根，那么4肯定也不会是。

我们要测试\(g^{7-1}\equiv 1\pmod{7}\)。

也还好，我们测试到3就行了：\(3^6\equiv 1\pmod{7}\)，所以3是对7求模的本征根。细心的朋友会发现，\(2^6\equiv 1\pmod{7}\)，为什么2不是？因为\(2^3\equiv1\pmod{7}\)，所以6不是最小的那个数字。

看来我们的测试出了一点问题：我们计算\(g^{p-1}\equiv 1\pmod{p}\)，但就算如此，也不能保证它是本征根，因为还有一个最小的、也就是秩的定义的要求。

让我们这样来考虑，一般而言对于一个素数来说，\(p-1\)是个偶数，是可以被分解的。比如对于11这个素数来说，\(p-1=10=2\times5\)，如果\(g^2\)或者\(g^5\)对11求模为1，那么很显然\(g^{10}\)也对11求模为1，但是这样的一个\(g\)不符合本征根的定义。

好，让我们从2开始：

\(2^2\equiv 4, 2^5\equiv 10\)，都不是1，再测试\(2^{10}\equiv 1\pmod{11}\)！Bingo！搞定了！

下一个要找的素数是13。\(13-1=12=2\times2\times3\)。

很幸运：\(2^2\equiv 4, 2^3\equiv 8, 2^6\equiv 12， 2^{12}\equiv 1\pmod{13}\)。所以，对13求模的本征根是2。

下一个是17。\(17-1=16=2\times2\times2\times2\)，它的因子有\(2, 4, 8\)。

\(2^2\equiv 4, 2^4\equiv 16, 2^8\equiv 1\)，不好！到了8次方就出现1了，所以2不是本征根。

\(3^2\equiv 9, 3^3\equiv 13, 3^8\equiv 16\)，妙极了！3是对17求模的本征根！

最后来看看19！\(19-1=18=2\times3\times3\)。它的因子是\(2, 3, 6, 9\)。

\(2^2\equiv 4, 2^3\equiv 8, 2^6\equiv 7, 2^9\equiv 18\pmod{19}\)，很好！2就是对19求模的本征根！

好了。求本征根的过程已经很明确了，总结如下：

1. 对\(p-1\)进行素数分解，找出所有的因子（注意，不只是质因子！）\({f_1, f_2, ..., f_k}\)，但不包括\(p-1\)（因为根据费马小定理，\(a^{p-1}\equiv 1\pmod{p}\)，但不一定\(p-1\)就是本征根）。
2. 从2开始，对所有的\(f\)计算\(2^{f_i}\)对\(p\)的模，如果为1，就可以停止运算。因为这个数字（2）肯定不是本征根，进入第4步。
3. 如果第二步计算中得到的模都不为1，那么这个数字就是本征根。
4. 换一个数字开始计算，一般就是加1。

虽然有了改善，但是我们看到，这个计算仍然非常繁琐。我的建议是，对于那些非常大的数字，用Wolfram来帮助计算会好一些。下面是一个截图：

从上面的练习我们也许可以猜想：每个素数都有至少一个本征根。确实如此。

定理6.8：每个素数\(p\)都有一个本征根。

这个定理现在我们还很难证明，还需要引入一些有关欧拉\(\phi\)函数的引理才行。

我们已经证明，对于\(p-1\)的任何因子\(d\)，最多有\(\phi(d)\)个互不同余的数字对\(p\)求模的秩是\(d\)。我们也知道对于每个自然数\(k\lt p\)，它有一个秩\(d\)，且\(d\mid p-1\)（定理4.16）。

我们用13这个数字来做个练习。

练习6.9：考虑素数\(13\)。对于\(13-1=12\)的因子\(d\in\{1, 2, 3, 4, 6, 12\}\)，在集合\(\{1, 2, 3, ..., 12\}\)中标出哪些数字具有的秩为\(d\)。

解：

让我们一个一个开始，以下列式中省去\(\pmod{13}\)的书写。

\(1^1\equiv 1\implies ord_{13}1=1\)

\(2^{12}\equiv 1\implies ord_{13}2=12\)

\(3^{3}\equiv 1\implies ord_{13}3=3\)

\(4^{6}\equiv 1\implies ord_{13}4=6\)

\(5^{4}\equiv 1\implies ord_{13}5=4\)

\(6^{12}\equiv 1\implies ord_{13}6=12\)

\(7^{12}\equiv 1\implies ord_{13}7=12\)

\(8^{4}\equiv 1\implies ord_{13}8=4\)

\(9^{3}\equiv 1\implies ord_{13}9=3\)

\(10^{6}\equiv 1\implies ord_{13}10=6\)

\(11^{12}\equiv 1\implies ord_{13}11=12\)

\(12^{2}\equiv 1\implies ord_{13}12=2\)

我们可以注意到一个事实：对于每个\(d\)，都恰好有\(\phi(d)\)个数字的秩是\(d\)，而且：

\(\phi(1)+\phi(2)+\phi(3)+\phi(4)+\phi(6)+\phi(12)=12\)，或者简写为：\(\sum_{d\mid n}\phi(d)\)。

引理6.11：如果\(p\)是一个素数，那么\(\sum_{d\mid p}\phi(d)=p\)。

证明：

显然，作为素数\(p\)，它的因子只能是1和\(p\)。而\(\phi(1)=1, \phi(p)=p-1\)。QED。

对于素数的幂次\(p^k\)来说，在\([1, p^k]\)（或者\([0, p^k-1]\)）的范围内，一共有\(p^k\)个数字，根据\(\phi\)函数的定义，和\(p^k\)不互质的数字有：\(0, p, 2p, 3p, ...\)，也就是每\(p\)个数有一个，也就是一共有\(\frac{p^k}{p}\)个，所以\(\phi(p^k)=p^k-p^{k-1}\)。

于是我们可以证明一个很重要的引理：

引理6.12：如果\(p\)是一个素数，那么\(\sum_{d\mid p^k}\phi(d)=p^k\)。

证明：

对于\(p^k\)而言，它的因子有：\(1, p, p^2, p^3, ..., p^{k}\)，我们有：

\(\phi(1)=1\\\phi(p)=p^1-1\\\phi(p^2)=p^2-p^1\\...\\\phi(p^k)=p^k-p^{k-1}\)

将这些式子累加得到\(\sum_{d\mid p^k}\phi(d)=p^k\)。QED。

我们在讨论新的引理前，先引入欧拉\(\phi\)函数的乘法表达式：

根据定义，\(\phi_p(m)\)等于小于等于\(m\)但无法被\(p\)整除的数的数量，从之前可以知道这样的数字每\(p\)个数出现一次，一共有\(\frac{m}{p}\)个，所以\(\phi_p(m)=m-\frac{m}{p}=m\times(1-\frac{1}{p})\)。

由此可以得到

引理6.13：如果\(p, q\)是两个不同的素数，那么\(\sum_{d\mid pq}\phi(d)=pq\)。

证明：（不会。略）

引理6.14：如果\(n, m\)是两个互质的素数，那么\((\sum_{d\mid m}\phi(d))\times(\sum_{d\mid n}\phi(d))=\sum_{d\mid mn}\phi(d)\)。

证明：（不会。略）

所有这些引理，可以导致我们本章的一个定理：

定理6.15：如果\(n\)是一个自然数，那么\(\sum_{d\mid n}\phi(d)=n\)。

以上定理还有另外一种证法。我们进行下一个练习。

练习6.16：对于任意一个自然数\(n\)，考虑其为分母的如下分数：\(\frac{1}{n}, \frac{2}{n}, ..., \frac{n}{n}\)。

比如令\(n=10\)，我们可以写下如下的最简分式：

\(\frac{1}{10}, \frac{1}{5}, \frac{3}{10}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{7}{10}, \frac{4}{5}, \frac{9}{10}, \frac{1}{1}\)。

我们可以注意到如下几个有趣的事实：

1. 所有10的因子（1,2,5,10）都出现在了分母上。
2. 10为分母的有几个？4个。这也是\(\phi(10)\)。因为根据\(\phi(n)\)的定义，既然有4个数字(\(k\in [1,10]\))与10互质，那么这几个数字作为分子，10作为分母的分数一定已经是最简分数。
3. 同样，5为分母的分数有4个，因为\(\phi(5)=4\)；而以2和1为分母的分数分别有1个和1个。
4. 以上几步中，我们建立了以\(n\)为底的最简分数和\(\phi(d)\)之间的一一对应关系。
5. 既然如此，\(\sum_{d\mid n}\phi(d)=n\)。

有了这些引理后，我们可以证明本章的一个重要定理。

定理6.17：每个素数\(p\)都有\(\phi(p-1)\)个本征根。

证明：

（没看懂。略）

欧拉的\(\phi\)函数是可乘的（multiplicative），根据这个特征，我们可以计算任意自然数的\(\phi\)值。

定理6.20：若\(n\)为一个自然数，而\(A\)是对\(n\)求模的完全余数集，那么\(A\)中与\(n\)互质的数字的数量就等于\(\phi(n)\)。

定理6.21：若\(n\)为一个自然数，\(k\)是一个整数，而\(m\)是一个与\(n\)互质的证书，那么集合\(\{k, k+m, k+2m, k+3m, .., k+(n-1)m\}\)构成对\(n\)求模的一个完全余数集。

这两个定理可以用来证明，两个互质的数字的乘积的\(\phi\)值等于这两个数字的\(\phi\)值的乘积，也就是：\(\phi(mn)=\phi(m)\phi(n)\)。

练习6.22：考虑两个互质的自然数9和4，在一个9*4的表格中，一次写下小于等于36的自然数，然后圈出和36互质的数字。

解：

\(\phi(36)=12\)，而\(\phi(4)=2, \phi(9)=6\)。

定理6.23：如果\(m, n\)是互质的两个自然数，那么\(\phi(mn)=\phi(m)\phi(n)\)。

定义：一个关于自然数的函数\(f\)是“可乘”的当且仅当对于任何一对互质的自然数\(m, n\)，有\(f(mn)=f(m)f(n)\)。

练习6.24：计算下列数字的\(\phi\)值。

\(\phi(3)=2\\\phi(5)=4\\\phi(15)=8\)

\(\phi(45)=\phi(5)\times\phi(9)=4*6=24\\\phi(98)=\phi(2)\times\phi(49)=\phi(7^2)=7^2-7^1=42\)。

\(\phi(5^{6}11^{4}17^{10})\)

由于\(5, 11, 17\)这三个数两两互质，所以可以拆开分别计算：

\(\phi(5^6)=5^6-5^5=12500\\\phi(11^4)=11^4-11^3=13310\\\phi(17^{10})=17^{10}-17^9=1,897,406,023,952\)

三个结果连乘得到：\(315,680,927,235,014,000,000\)。大家可以在WolframApha中自行验证。

本章后续集中在利用欧拉定理来找到形如\(x^k\equiv b\pmod{n}\)的解。

练习6.28:选择几个\(a\)，计算一下\(a^9\pmod{5}\)，看看能不能找到一些规律。再试试\(a^{17}\pmod{15}\)。

解：

列表如下

\(a\)	\(a^9\)	\(a^9\pmod{5}\)
1	1	1
2	512	2
3	19683	3
4	262144	4
5	1953125	0
6	10077696	1
...	...	...

\(a\)	\(a^{17}\)	\(a^{17}\pmod{15}\)
1	1	1
2	131072	2
3	129140163	3
4	17179869184	4
5	.....	5
6	.....	6
7	.....	7
...	...	...

定理6.29：如果\(a\)是一个整数，而\(v, n\)是自然数，且\((a, n)=1\)，那么\(a^{v\phi(n)+1}\equiv a\pmod{n}\)。

接下来我们用这个定理来做一些题目。

练习6.30：\(x^5\equiv 2\pmod{7}\)。

解：

充分考虑定理6.29的形式，我们可以看到，\(n=7, \phi(7)=6\)。\(v\phi(n)+1=v\times 6+1=5\implies v=\frac{2}{3}\)，和定理6.29的要求不符合。

我们继续考虑\(x^{10}\equiv 4\pmod{7}\)。\(v\phi(n)+1=v\times6+1=10\)，还是无解。

继续：\(x^{15}\equiv 8\pmod{7}\)。\(v\times 6+1=15\)，无解。

\(x^{20}\equiv 16\implies v\times 6+1=20\)，无解。

\(x^{25}\equiv 32\implies v\times 6+1=25\implies v=4\)。

\(32^{4*6+1}\equiv 32\equiv 4\pmod{7}\)，而且\((32, 7)=1\)。但这不是我们的答案。

\(32^{25}=2^{2+123}\)，而我们可以很快知道\(2^3\equiv 1\pmod{7}\implies 2^{123}\equiv 1\pmod{7}\)。所以\(4^{0\times6+1}\)是符合定理6.29格式的一个解。

我们试算\(4^5=1024\equiv 2\pmod{7}\)，题设要求成立，所以\(x=4\)。

练习6.31：求\(x^3\equiv 7\pmod{10}\)

解：这个求解其实不难，我们很快就知道\(x=3\)是解。不过我们还是来系统性地求解。

本题中，\(n=10, \phi(10)=4\)。

\(v\phi(n)+1=v\times 4+1=3\implies v=\frac{1}{2}\)，不符合定理6.29的形式。

考虑\(x^6\equiv 49\pmod{10}\)。\(v\times 4+1=6\)，无解。

\(x^9\equiv 343\pmod{10}\)。\(v\times 4+1=9\implies v=2\)。

\(343^9\equiv 343\pmod{10}\)。我们继续约简。

\(343^9=(7^3)^9=7^{27}=7^3\times7^{24}\)。

而\(7^{24}=(7^4)^6\equiv 1\pmod{10}\)，所以\(7^3\equiv343\pmod{10}\)。

将\(7^3\)代入原式：\((7^3)^3\equiv 7\pmod{10}\)。所以\(x=7^3\)。

这个数字比我们心算得到的\(x=3\)大了很多，肯定哪里出了错。（残念！）

定理6.32：如果\(k, n\in\mathbb{N}\)，且\((k, \phi(n))=1\)，那么存在正整数\(u, v\)使得\(ku=\phi(n)v+1\)。

证明：

这个定理证明不难，因为\((k, \phi(n))=1\)，所以一定存在\(uk+(-v)\phi(n)=1\implies ku=\phi(n)v+1\)。

练习6.33：进行如下计算

1. \(x^7\equiv 4\pmod{11}\)
2. \(x^5\equiv 11\pmod{18}\)
3. \(x^7\equiv 2\pmod{8}\)

解：

第一题：\(n=11\implies \phi(11)=10, k=7, (7,10)=1\)，根据定理6.32，我们来找到\(uk+(-v)\phi(n)=1\implies ku=\phi(n)v+1\)中的\(u, v\)。简单试算得到\(7\times 3=10\times 2+1\)。（下来不会了。）

但通过简单试算可以知道\(9^7\equiv 4\pmod{11}\)。