本页面已浏览183次

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来帮助计算会好一些。下面是一个截图:

Finding primitive root with 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)$

\(\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}\)

Previous Post