附录：数学基础

四川大学1/72上周讲到……应用密码学(数论、有限域和计算复杂性基础)四川大学电子信息学院2/72一、数论基础整数具有以下性质：（1）b|a，c|b，则c|a（2）a|1，则a=±1（3）对任一b（b≠0）,b∣0（4）b|g，b|h，则对任意整数m,n有b|(mg+nh)定理1：任给两个整数a，b，其中b>0，则存在两个唯一的整数q和r，使得

a=qb+r，0≤r＜b

成立。余数，也叫做非负最小剩余不完全商1.素数与互为素数

整除与因子的概念：

任给两个整数a，b，其中b≠0，如果存在一个整数q使得等式

a=q

b

成立，此时称b整除a，记为b|a，并称b为a的因子，把a为b的倍数。否则b不整除a，记为b

a∣四川大学电子信息学院3/72

最大公因数与辗转相除法定义：设a1，a2，…，an是n个不全为零的整数，若整数d（通常考虑d>0）是它们之中每一个的因数(子)，那么d就叫做设a1,a2,……,an的一个公因数。公因数只有有限个，其中最大的一个公因数叫最大公因数(子)。

记为：（a1,a2,……,an

），若（a1,a2,……,an

）=1，则称a1，a2，…，an互素。

对于整数a,b，其最大公因数等价的定义形式是：（a,b）＝max{k，k|a且k|b}注意：（a,b）=（－a,b）=（a,－b）=（|a|，|b|）定理2：设a,b,c是任意不全为零的整数，且

a=qb+c；其中q是整数，则有（a,b）=（b,c）。即被除数和除数的最大公因子与除数和余数最大公因子相同。a

除以b,商q余c例：(18,12)=(12,6)=(6,0)=6(11,10)=(10,1)=(1,0)=1四川大学电子信息学院4/72辗转相除法:（Euclid算法，欧几里德算法）任给两个整数a，b，设a>b>0，由代余数的除法，有下列等式：

a=bq1

+r1

，0<r1

＜b，

b=r1q2+r2

，0<r2

＜r1

，

……（1）

rn-2=rn-1qn+rn

，0<rn

＜rn-1

rn-1=

rnqn+1

+rn+1

，rn+1=0

因为b>r1>r2>r3>…,故经有限次代余数除法后，总可以得到一个余数是零，即上式中rn+1=0。定理3：任给整数a>b>0，则（a,b）就是（1）中最后一个不等于零的余数，即（a,b）=rn

（举例）定理4：任给整数a>b>0，则存在两个整数m,n

使得（a,b）=m

a+n

b

由上式，显然有推论：a和b的公因数是(a,b)的因数。转一次不定方程5/72288=158×1+130，

158=130×1+28，

130=28×4+18，

28=18×1+10，

18=10×1+8，

10=8×1+2，

8=2×4+0因此，最大公因数(a,b)=2

再进行逆向迭代，2=10－8×1(代2)=10－(18－10)×1(代8)=10×2－18=(28－18×1)×2－18(代10)=28×2－18×3 =28×2－(130－28×4)×3(代18)=28×14－130×3=(158－130×1)×14－130×3(代28)=158×14－130×17=158×14－(288－158×1)×17(代130)=158×31－288×17=－17×288+31×158所以m=－17,n=31例：用辗转相除法求，a=288，b=158的最大公因数和m,n，使ma+nb=(a,b)四川大学电子信息学院6/72最小公倍数：

素数(质数)的概念：

大于1的整数被称为素数是指p的因子仅有1,－1,p,－p。定义：若（a，b）=1，则a与b互素。引理1：若p是素数，a是任意整数，则有p|a

或(p,a)=1

即素数与一个数要么互素，要么可整除该数。引理2：若p是素数，p|ab，则p|a

或p|b四川大学电子信息学院7/72定理5：任一整数a(a>1)都能唯一地分解为以下形式：

（整数的惟一分解性定理）推论1：若d|a，则d一定有形式：如整数120的所有因子可表示为：转一次不定方程四川大学电子信息学院8/72

有50个队员，分别编号为1、2…、50；另有50盏电灯（为拉线式开关），分别编号为(1)、(2)…、(50)。规则：若某灯的编号正好是某队员编号的倍数，则该队员就拉该灯一次。

如1号队员将对50个灯都拉一次；

3号队员将拉(3)、(6)、(9)、……(45)、(48)号灯各一次；

……50号队员将只拉(50)号灯一次；问题：最后有哪几盏灯是亮的?（设初始为全熄）。结果：共7盏灯是亮的。即：

(1)，(4)，(9)，(16)，(25)，(36)，(49)一个趣味问题推论2：a是一个完全平方数D(a)是奇数。——“拉灯”问题：定理5四川大学电子信息学院9/722.一次不定方程二元一次不定方程是指：

a1x+a2y=n（1）其中a1，a2，n是给定的整数，a1，a2≠0定理6：方程(1)有解的充分必要条件是：

(a1，a2)|n由前面定理4，当(a1，a2)=1，存在整数s，t使：

sa1+ta2=(a1，a2)=1两边乘以n，sna1+tna2=n与(1)式比较，有解：x0=sn，y0=tn

，充分条件得证。此为方程(1)的一组特解，而全部解可由下面定理给出：定理7：(a1，a2)=1，则方程(1)一定有解，且全部解（通解）为：转同余方程（组）x=x0+a2ky=y0

－a1k其中，kZ，x0,y0是方程(1)的一组特解。（证明略）证明：式(1)有解→(a1，a2)|n显然成立，必要条件得证。当(a1，a2)|n，不失一般性，可假设(a1，a2)=1,a1>0，a2>0

四川大学电子信息学院10/72

得s=－2，t=3所以所求特解为：

x0=－2×24=－48，

y0=3×24=72

所以，方程的完全解为：

x

=x0+a2k=－48+7ky

=y0－a1k=72－10k其中kZ

【例】解方程10x+7y=24解：此例，a1=10，a2=7，n=24，因为(10,7)=1所以方程有解。由辗转相除法计算满足下式的s和t：10s+7t=1，有10=7×1+37=3×2+11=7－3×2=7－(10－7×1)×2=10×(－2)+7×3四川大学电子信息学院11/723.模运算与同余式定义：设n是一正整数，a是整数，如果用n除a，得商为q，余数为r，则

a=qn+r，0≤r≤n，q=a/n其中，x为小于或等于x的最大整数。用amodn

表示余数r，则a=a/nn+amodn

如果(amodn

)=(bmodn)，则称两整数a

和b

模n

同余，记为：

a≡bmodn

称与a模n同余的数的全体为a的同余类，记为[a]，并称a为该同余类的表示元素。（显然，同余类中的每一元素都可作为这个同余类的表示元素）

如果a≡0modn

，n|a四川大学电子信息学院12/723.模运算与同余式（续）

(2)同余的性质：如果(amodn

)=(bmodn)，则a≡bmodn；(定义)自反性：

a≡amodn；

对称性：如果a≡bmodn，则b≡amodn；

传递性：如果则a≡bmodn，b≡cmodn，则a≡cmodn；

四川大学电子信息学院13/72如果n|(a－b)，则a≡bmodn

；证明：必要性：设a≡bmodn，则有a=k1n+r，b=k2n+r，0≤r＜n故a－b=n(k1－k2)

显然有，n|(a-b)

充分性：设

a=k1n+r1，b=k2n+r2，0≤r1＜n，0≤r2＜n

有

a－b=n(k1－k2)+r1－r2，如果有，n|(a－

b)，必有

n|(r1－r2)

，而

|r1－r2|<n

所以

r1=r2，即a≡bmodn

a,b对模n同余的充要条件：返回模运算性质四川大学电子信息学院14/72(3)模运算及性质：模运算性质：模n下的算术运算性质

下面设a,b,c,d都是整数，而n为正整数，有模运算性质：

(a±b)modn=[(amodn)±(bmodn)]modn

证明：设amodn=ra，bmodn=rb，有：

a

=jn+ra，b

=kn+rb，j，k分别为两个整数。有：

(a±b)modn=(jn+ra±kn±rb)modn =(ra±rb+jn±kn)modn=(ra±rb)modn=[(amodn)±(bmodn)]modn

(a×b)modn=[(amodn)×(bmodn)]modn

概念：求余数运算amodn

将整数a映射到非负整数集合Zn={0,1,…,n-1}，称为求余运算，在这个集合上的运算称为模运算。四川大学电子信息学院15/72交换律:

(a*

b)modn=(b*

a)modn

;“*”可为+、×结合律:

[

a*(

b*

c)]modn=[(

a*

b)

*

c]modn

;“*”可为+、×分配律:

[

a×(

b+c)]modn=[

a×b+a×c)]modn恒等:

(0

+

a)modn=

(1×a)modn=a

modn加法逆元:

对每一个w∈Zn

，存在一个u，使得

w+u＝0modn

记为，u=－w，显然:

在模n下，－w＝n－w满足交换律、结合律、分配律、恒等、加法逆元。（证明略）模运算性质(续)四川大学电子信息学院16/72如果

a≡bmodn

c≡dmodn

则有(1)(a±c)≡(b±d)modn

；特例：a±c≡b±cmodn

更一般式：(ax

＋

cy)≡(bx

＋dy)modn

x,y

∈Z

(2)ac≡bdmodn

；特例：ac≡bcmodn

(3)

f(a)≡f(b)modn

其中f(x)为任给定的一个整系数多项式证(1)：因为n|(a－b)，n|(c－d)，故n|[x(a－b)＋y(c－d)]

即，n|[(ax＋cy)－(bx＋dy)]

即(ax＋cy)≡(bx＋dy)modn证(2)：由n|[c(a－b)＋

b(c－d)]

即n|[ac

－bd)]所以ac≡bdmodn模运算性质(续)四川大学电子信息学院17/72解：实际上是要证明： 560≡1(mod56),223≡1(mod47)(1)有：560=

(

56)10=(53)2)10≡(((53)mod56)2)mod56)10(mod56)

而53=125≡13(mod56) 于是

(53)2≡169≡1(mod56)∴(53)2)10≡1(mod56)，于是有：56∣560－1。

(2)有：223=(26)32526=

64≡17mod(47)(26)3≡173≡25mod(47)∴

(26)3·25≡25×32≡1mod(47)

于是有：47∣223－1

转同余充要条件【例1】通过同余式演算证明:560－1是56的倍数，223－1是47的倍数。四川大学电子信息学院18/72【例2】证明：正整数N被9整除的充要条件是N的各位数字(10进制)的和被9整除。证明：

实际上是要证明正整数N

与N的各位数字的和在模9下同余。设N=a0+10a1+102a2+……+10kak，将N看成是10的整系数多项式,

f(ｘ)＝a0+ｘa1+ｘ2a2+……+ｘkak

N记为：N=f(10)，显然有：f(1)=a0+a1+a2+……+ak

有10≡1mod9

由模运算性质，有f(10)≡f(1)mod9

即：N≡a0+a1+a2+……+akmod9四川大学电子信息学院19/72证明:

(返回Euler定理)如果(ab)≡(ac)modn，且(a,n)=d，则（乘法的消去律）如果(a＋b)≡(a＋c)modn，则b≡cmodn；(加法的可约律)

例如：(5＋

23)≡(5＋

7)mod8，23≡7md8

定理8：加法的可约律与乘法的消去律四川大学电子信息学院20/72推论1：如果(ab)≡(ac)modn，且(a,n)=1，则b≡cmodn。（消去律）推论2：

如果

(a,n)=1，则a×Zn=Zn

。

这里，a×Zn表示a与中每一元素做模n乘法。定义：模n下的乘法逆元：如果，(a,n)

=1，则a在modn下有存在一个x(x<n)，使得ax≡1modn，x称为a在模n下的乘法逆元。

记为，x=a－1mod

n逆运算性质：(a×b

)－1=a－1×b－1modn

证明:设t=(a×b

)－1modn，有

t－1=a×b

modn，再由模运算性质有：

a－1×b－1×t－1=a－1×b－1×a×b≡

1

modna－1×b－1=t=(a×b

)－1modn(返回Euler定理)

定理8：加法的可约律与乘法的消去律（续）21/72用辗转相除法求乘法逆元：（扩展的Euclid算法）要点：按前面定理4，任给整数n>a>0

，，则存在两个整数x,y使得

xa+yn=(a,n)当(a,n)=1时，即有xa+yn=1等式两端取模n，有xamodn=1

即存在一个x，使得ax≡1modn。如何求x?

————

用辗转相除法求乘法逆元，即扩展的Euclid算法【例】计算550－1mod1769有x=550,y=－171所以550－1mod1769=550

1769=550×3+119，1=13－3×4(代3)550=119×4+74，=13－(16－13×1)×4=13×5－16×4(代13)119=74×1+45，=(29－16×1)×5－16×4=29×5－16×9(代16)74=45×1+29，=29×5－(45－29×1)×9=29×14－45×9(代29)45=29×1+16，=(74－45×1)×14－45×9=74×14－45×23(代45)29=16×1+13，=74×14－(119－74×1)×23=74×37－119×23(代74)16=13×1+3=(550－119×4)×37－119×23=550×37－119×171(代119)13=3×4+1=550×37－(1769－550×3)×171=550×550－1769×171正向迭代过程逆向迭代过程四川大学电子信息学院22/724.剩余类与完全剩余类全体整数：Z={0,±1,±2,±3……}，前面已定义：a∈Z，称与a模n同余的数的全体为a的同余类，显然全体整数模n的同余类共有n个，他们分别为nk+0，

nk+1，

nk+2，…

nk+(n-1)，(k∈z)，共n类；若取n=4，整数分为4类：

C0={4k|k∈Z}C1={4k+1|k∈Z}C2={4k+2|k∈Z}C3={4k+3|k∈Z}

所以，当n>1时，整数分为n类：C0

，C1

，……，Cn-1

Cj={nk+j|k∈Z}；j=0,1,2,……,n－1称Cj为模n的一个剩余类（即“一类余数”）。四川大学电子信息学院23/724.剩余类与完全剩余类（续）

若从所有剩余类C0

，C1

，……，Cn-1类中各取一个数构成集合，该集合则称为模n的一组完全剩余系。显然，这样的集合有无数个，而最简单的完全剩余系为：0,1,2,……,n－1称为非负最小完全剩余或标准完全剩余系。如，Z模12的标准剩余系为：0,1,2,3,4,5,6,7,8,9,10,11定理9：设a1，a2

，……，an是模n的一组完全剩余系。有整数k，且(k,n)=1，则

k

a1，k

a2，……，k

an也是一组完全剩余系。

24/725.费马(Fermat)小定理与欧拉(Euler)定理

(这两个定理在公钥密码体制中起着重要作用)定义：如果一个模n的剩余类里面的数都与n互素，就把该剩余类称为与模数n互素的剩余类。如n=4，C3={4k+3|k∈Z}，C3为与模数4互素的剩余类在与模数n互素的的全部剩余类中，各取一数所组成的集合叫模n的一组缩系。如{1，3}为模4的一组缩系。定义：欧拉函数(n)是一个定义在正整数集上的函数，(n)的值等于小于n且与n互素的正整数的个数。欧拉函数：例如：(4)=(6)=2，(7)=6，(8)=4，25/72欧拉函数(续)定理：设整数n

(>1)的唯一性分解形式为：例如，n=120736=25×73×11(n)=24×72×6×10=47040

26/72特别，当p是一个素数，有(p)=p－1

当n是两个素数p和q的乘积，则对n=pq，有

(n)=(pq)=(p)(q)=(p－1)(q－1)

证明：考虑模n的标准完全剩余系为{0，1，…，(pq－1)}，而不与n互素的元素包括：p因子集合{p，2p，…，(q－1)p}，q因子集合{q，2q，…，(p－1)q}和0。因此，有：

(n)=pq－[(q－1)+(p－1)+1]=pq－(p+q)+1

＝(p－1)(q－1)=(p)(q)例如：(21)＝(3×7)=(3)×(7)＝(3－1)×(7－1)＝2×6=12欧拉函数(续)四川大学电子信息学院27/72证明：当x过模n的一组缩系，则ax通过(n)个整数，由于（a，n）=1，（xi，n）=1

所以，（axi，n）=1i,j=1,2,….(n)

若

axi=axj，可得axi≡

axj

modn与所设

x过模n的一组缩系矛盾，故ax也过n的一组缩系。定理12：若（a，n）=1，x过模n的一组缩系(即x取x1，……，x(n)

，且xi与n互素),则ax也过n的一组缩系。定理11：

若a1，……，a(n)

是(n)个与n互素的整数，则a1，……，a(n)

是模n的一组缩系的充要条件是它们两两对模n不同余。（从定义看，定理10，11时显然的）定理10：模数n的一组缩系的元素个数为(n)。四川大学电子信息学院28/72定理13

：若p是素数，且不能整除a，则有：

a

p－1

≡1modp或

a

p≡amodp

显然，a

k(p－1)

≡1modp

∴aN=ak(p－1)+r≡aNmod(p－1)

modp

费马小定理应用举例：计算7560mod31=?7560=7560mod(31－1)

=7(31－1)×18+20

≡720

mod31

≡75×75×75×75mod31≡5×5×5×5≡5mod31费马小定理29/72证明：设r1，……，r(n)

是模n的一组缩系，则由定理12，ar1，……，ar(n)

也是模n的一组缩系，故

(ar1)(ar1)……(ar(n))≡r1……r(n)modn即a

(n)

r1……r(n)

≡r1……r(n)modn由于(ri,n)=1i=1,2,….(n)

故(r1……r(n),n)=1由定理8的推论1（消去律），有：a

(n)

≡1modn得证定理14（Euler定理）：设n,a∈Z，且(a，n)=1，则a

(n)≡1modn如，a=3，n=10；→

(10)=4，34=81≡1mod

10

a=2，n=11；→

(11)=10，210=1024≡1mod

11

30/72

有

a

k(n)+1

≡amodn(k∈Z)Euler定理的推论

:

给定两个素数p,q，以及整数n=pq和m，其中0<m<n，则对于任意整数k，有下列关系成立：

m

k(n)+1=

m

k(p－1)(q－1)+1

≡mmodn(Euler定理要求(a，n)=1，而其推论将a的条件放宽，可用于说明RSA密码算法)由

a

(n)≡1modn等价形式：四川大学电子信息学院31/72

定理15：设(a，n)=1，n>0，则同余式：

ax

≡b

modn恰有一个解。而x=ba(n)－1

就是其唯一解。(a－1

≡a(n)－1modn)

思路：让x过模n一个完全剩余系，x=b1,b2,….,bn－1，

ax=ab1,ab2,….,abn－1，

因为(a，n)=1，所以ax也过一个完全剩余系故一定有一个xi，使axi

=bmodn

故有解(其解可代入证明)

定理16：设n>0，则同余式：

ax

≡b

modn有解的充要条件是：(a,n)|b

且恰有(a,n)个解。

6.同余方程（组）与中国剩余定理四川大学电子信息学院32/72

例:(1)求2x

≡179

mod562的整数解。(2)求256x≡179mod337的整数解。因为(256,337)=1,所以同余式有一个整数解。解法1：∵(256,337)=1∴256在模337有逆元存在。

256－1

mod337=104

用104乘以同余方程两边，有

104×256x

≡104×179

mod337

即x

≡104×179≡81mod

337解法2：考虑二元一次不定方程：256x+337y=179…….(1)

由不定方程有解的充要条件，当(256,337)=1,则一次不定方程(1)一定有解。利用扩展的Euclid算法，不定方程(1)的一组特解为：

x0=104×179y0=－79×179显然，对式(1)等式两端取mod337，即为同余式256x

≡179

mod337所以得同余式解：x

=104×179≡81mod

337因为(2,562)=2,而2|179,故同余式没有整数解。四川大学电子信息学院33/72例子：（孙子算经）今有物不知其数；三三数之余二；五五数之余三；七七数之余二。问物几何？设x为所求未知数。原问题为求解同余方程组：

对此方程组的一般解法，在明朝程大位的“算法统宗”(1593)里有一首歌谣给出了答案：

三人同行七十稀，五树梅花廿一枝，

七子团圆月正半，除百零五便得知。

其解为：x

≡70×2+21×3+15×2mod105=23一般应如何求解同余方程组？中国剩余定理四川大学电子信息学院34/72(1)[3，5]=15，15mod7=1→15×2mod7=2(2)[3，7]=21，21mod5=1→21×3mod5=3[5，7]=35，35mod3=2→35×1mod3=2显然，15×2+21×3+35×1=128是一个解（但还不是最小解）有：128±k×[3,5,7]=233+k×105；k∈Z

所以最小正整数解为：x=23普通解法：四川大学电子信息学院35/72

设m1,m2,……mk是k个两两互素的正整数，并记M=m1m2……mk，Mi=M/mi，则同余方程组：在模M同余的意义下有唯一解：

x≡M1M1’b1＋M2M2’b2＋……＋MkMk’bkmodM（2）其中MiMi’≡1modmi定理17（中国剩余定理，CRT-ChinaResidueTheorem）：第2周（1）四川大学电子信息学院36/72定理17（中国剩余定理证明）：证明：由于(mi,mj)=1，i≠j，所以(Mi,mi)=1

注意到M=Mimi所以当

i≠j，mi|Mj，即Mj≡0modmi，故

M1M1’b1＋M2M2’b2＋……＋MkMk’bk（应用模运算性质）≡MiMi’bi≡bimodmi故(2)为(1)的解

(注意：MiMi’≡1modmi)另外，设整数y

也能同时满足式(1)，由于(2)式是满足(1)的正整数解，即

y≡xmodm1，y≡xmodm2，……，y≡xmodmk，也即，m1|(x－y)，m2|(x－y)，……，mk|(x－y)由于m1,m2,……mks两两互素，所以(m1m2……mk)|(x－y)

所以x≡ymodM即在模M同余的意义下(2)是唯一解。第2周四川大学电子信息学院37/72【举例】11数剩3，12数剩2，13数剩1，求本数。解：依题意有，即m1

=11，m2

=12，m3

=13，b1

=3，b2

=2，b3

=1，此时有：M=11×12×13=1716，

M1

=1716/11=156，M2

=1716/12=143，M3

=1716/13=132而M1’为一正整数，它满足：M1M1’≡1mod11，即1≡M1M1’≡156M1’mod11≡2M1’mod11，易得M1’=6(可用扩展Euclid算法求得：M1’=M1－1modm1

=156－1mod11

=2－1mod11

)

同理，可求出：M2’=11，M3’=7由CRT，得解：x≡b1M1M1’＋b2M2M2’＋b3M3M3’≡3×156×6+2×143×11+1×132×7≡14mod1716所以，完全解为：x=14+1716kk∈Z

四川大学电子信息学院38/72中国剩余定理的主要应用：1、求解同余方程组（模M下的唯一解）；2、在模M下可将一个非常大的数N，用一组较小的数组成的k元组(b1，b2，……，bk)来表达。且在模M下，N与(b1，b2，……，bk)唯一对应。3、ZM上元素的运算等价于k元组对应元素之间的运算，即如果：

A←→(a1，a2，……，ak)，B←→(b1，b2，……，bk)

则(A+B)modM←→[(a1

+b1)modm1，……，(ak

+bk)modmk

](A－B)modM←→[(a1

－b1)modm1，……，(ak－bk)modmk

](A×B)modM←→[(a1×b1)modm1，……，(ak×bk)modmk

]四川大学电子信息学院39/72中国剩余定理的主要应用（续）

例:将973mod1813用模数为37和49的两个数表示（1813=37×49）。解：可取N=973，M=1813，m1

=37，m2

=49，有：b1=Nmodm1

=973mod37=11

b2=Nmodm2

=973mod49=42

所以973←→(11，42)若要计算973mod1813+678mod1813，则可先求出：

678←→(678

mod37,678

mod49)即678←→(12,41)，应用上面性质可得加法表达为：

[(11

+12)mod37,(42

+41)mod49]=(23，34)四川大学电子信息学院40/727.离散对数

1）求模下的整数幂由Euler定理，如果(a,n)=1，则a

(n)

≡1modn现考虑一般形式，

a

m

≡1modn；m为一正整数(1)如果(a,n)=1，则至少有一整数m

(m=(n))满足该方程。定义：满足式(1)的最小正整数m为模n下a的阶(又称次数)。例：

a=7，n=19，则易求出

7

1

≡7mod

19

，7

2

≡11mod

19，7

3

≡1mod

19，

即7在模19下的阶为3。四川大学电子信息学院41/727.离散对数

1）求模下的整数幂(续)由于7

3k＋j

≡7

3k×7j

≡7

jmod

19

所以，74

≡7mod19，75

≡72mod19，……，即从74mod19开始，所求的幂出现循环，循环周期为3，即等于元素7在模19下的阶。性质1：a的阶m

整除(n)

，即m|

(n)

（注意：(a,n)=1

）证：若m不能整除(n)

，可令(n)=km+r，其中

0<r≤m－1，那么由Euler定理：a

(n)=a

km+r=(a

m)ka

rmodn≡a

rmodn≡1modn

即

a

r

≡1modn与m是模n下a的阶矛盾。

实际上，任意满足式(1)的整数m一定是a的阶的倍数。

四川大学电子信息学院42/72定义：如果a的阶等于(n)

，则称a为n的本原元（又称为素根）。特别地，如果a是素数p

的本原元，则

a,a2,…,ap－1(p-1)个数在模p下互不相同，且均与p互素。性质2：如果a是n的本原元，则

a,a2,…,a(n)在模n下互不相同，且均与n互素。证明：因为a,n互素，ak与n互素显然。设ai

≡aj

modn

；0

≤i<j≤

(n)－1

有1

≡aj－imodn

j－i﹤(n)

与(n)

是a的阶矛盾。四川大学电子信息学院43/72定义：如果a的阶等于(n)

，则称a为n的本原元（又称为素根）。例：n=9，(n)

=6，考虑a=2的情况

（显然(2,9)=1，但9不是素数）

21mod9＝2，22mod9＝4，23mod9＝8，

24mod9＝7，25mod9＝5，26mod9＝1，显然，2模9的下的阶为(9)

=6，所以2为9的本原元。注意:模n下的本原元不具备唯一性。

例如，a=2、3、10、13、14和15都是模19的本原元。一个有用的结论：并非所有的模n都有本原元，只有以下形式的模n才有本原元：

2，4，p，2p；其中p为奇素数。四川大学电子信息学院44/72

2）离散对数（1）一般对数的概念指数函数y=ax(a﹥0,a≠0)的逆函数称为以a为底x的对数，记为：y=logax

有性质：loga1=0，logaa

=1，

logaxy=logax+logay，

logaxy=ylogax四川大学电子信息学院45/72（2）离散对数的概念设p为一素数，a是p的本原元，则a,a2,…,ap－1

产生1到p－1之间的所有值，且每一值仅出现一次。因此：对于任意b∈{1,…,p-1}，都存在惟一的i(0≤i≤p-2),

使得

b≡a

imodp则称i为模p下以a为底b的指数，记为：

i=inda,p(b)；也把这样的指数称为离散对数显然，指数有性质:(1)inda,p(1)=0；

(2)inda,p(a)=1；

2）离散对数（续）注意：a

p－1≡1modp∴inda,p

(1)=p-1

为和一般对数一致，取inda,p

(1)=046/72

以上定义，假定模数p

为素数，对于非素数指数也有类似定义。但数b的取值不再是b∈{1,…,p-1}。

指数性质(3):若a

x

≡a

ymodn，其中a，n互素，a是n的本原元，则有：x

≡

y

mod

(n)

(可看成是ax

,ay

分别取离散对数)证明：因a，n互素，所以a在模n下存在逆元a－1

，在a

x

≡a

ymodn两边同乘以(a－1)y，得

a

x－y

≡1modn由Euler定理，a

(n)

≡1modn，而a是n的本原元，知存在一整数k，使得x－y

=k

(n)

，即

(n)|(x－y)，所以，x

≡

ymod

(n)

离散对数的概念（续）47/72由性质(3)可得以下两个性质：性质(4):inda,p(xy)=[inda,p(x)+inda,p(y)]mod

(p)

性质(5):inda,p(xy

)=[y×inda,p(x)]mod

(p)

离散对数的概念（续）四川大学电子信息学院48/72

设p是素数，a是p的本原元，即a,a2,…,ap－1在modp下产生1到p-1的所有值，所以对任意b∈{1,…,p-1}，有惟一的

i∈{1,…,p-1}使得

b≡a

imodp(1)

称i为模p下以a为底b的离散对数（指数），记为

i=inda,p(b)(2)重要特性：当a、p和i已知时，对式(1)可有快速算法比较容易地求出b；但如果已知a、b和

p，要由式(2)求i则非常困难。尤其是当p很大时(如150位以上)，求离散对数计算不可行。

由以上性质可见离散对数与一般对数的概念极为相似，下面再强调给出有关离散对数的定义:

四川大学电子信息学院49/728.平方剩余设p是一素数，a小于p，称a是p的平方剩余（二次剩余），如果方程x2≡a(modp)有解，否则称为非平方剩余。例如：x2≡1mod7有解x=1，x=6；

x2≡2mod7有解x=3，x=4；

x2≡3mod7无解；

x2≡4mod7有解x=2，x=5；

x2≡5mod7无解；

x2≡6mod7无解。可见共有3个数（1，2，4）是模7的平方剩余，且每个平方剩余都有两个平方根（既例中的x）。定理：设p是素数，a是一整数，a是p的平方剩余的充要条件是：

a(p－1)/2≡1

modp

a是p的非平方剩余的充要条件是：

a(p－1)/2≡－1

modp【例如】，p=23，a=5,a(p－1)/2≡511modp=－1所以，5不是模23的平方剩余。实际上。在模p的缩系1，2，….，p－1中，有(p－1)/2个模p的平方剩余，和(p－1)/2个模p的非平方剩余。四川大学电子信息学院50/72勒让德符号定义：设p是素数，a是一整数，符号的定义如下：称符号为Le