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\)求模的本征根。

Next Post