密码学-第4章数论与有限域基础

第一部分

第四章数论与有限域基础张权2012年秋季本章提纲数论基础群、环、域有限域基础数论基础素数与互素对整数b!=0及a，如果存在整数m

使得a=mb，称b

整除

a，也称b

是a

的因子，记作b|a

例1,2,3,4,6,8,12,24整除24整除具有以下性质：如果a|1，那么a=±1如果a|b

且b|a，则a=±b对任一b(b≠0)，b|0如果b|g，b|h，则对任意整数m、n

有b|(mg+nh)数论基础素数与互素称整数

p(p>1)

是素数，如果

p

的因子

只有±1，±p任一整数

a(a>1)

都能惟一地表示为以下形式：

其中

p1

>

p2

>

…>pt

是素数，αi

>0(i=1,…,t)。

例如：91=7×13，11011=7×112×13数论基础素数与互素该性质称为整数分解的惟一性，也可如下陈述：设P是所有素数集合，则任意整数a

(a>1)都能惟一地写成以下形式：

其中ap≥0，等号右边的乘积项取所有的素数，然而大多指数项ap为0。相应地，任一正整数可由非0指数列表表示。

例如：11011可表示为{a7=1,a11=2,a13=1}。数论基础素数与互素称c

是两个整数a、b

的最大公因子，当且仅当：

①c

是a

的因子也是b

的因子，

即c

是a、b

的公因子

②a

和b

的任一公因子，也是c

的因子表示为c=gcd(a,b)数论基础素数与互素由于最大公因子为正，所以

gcd(a,b)=gcd(a,-b)=gcd(-a,b)=gcd(-a,-b)一般地gcd(a,b)=gcd(|a|,|b|)由任一非0整数能整除0，可得gcd(a,0)=|a|如果将a，b都表示为素数的乘积，则gcd(a,b)极易确定。例如：300=22×31×52；18=21×32，所以gcd(18,300)=21×31×50=6一般地，由c=gcd(a,b)可得：对每一素数p，

cp

=min(ap,bp)数论基础素数与互素如果gcd(a,b)=1，则称a和b互素整数a,b

互素是指除1之外它们没有其它公因子，例如：8与15互素8的因子：1,2,4,815的因子：1,3,5,151是8与15唯一的公因子数论基础模运算设n

是一正整数，a是整数，如果用n

除a，得商为q，余数为r，则

其中为小于或等于x的最大整数。用amodn表示余数r，则如果(amodn)=(bmodn)，则称a

和b

(模n)同余，

记为a≡bmodn。与a

模n

同余的数的全体称为a

的同余类，记为[a]，称a

为这个同余类的表示元素。注意：如果a≡0(modn)，则n|a。数论基础模运算同余有以下性质：①若

n|(a-b)，则

a≡bmodn②a≡bmodn，则

b≡amodn③a≡bmodn

且b≡cmodn，则

a≡cmodn从以上性质易知，同余类中的每一元素都可作为这个同余类的表示元素。数论基础模运算求余数的操作a

modn

将整数

a

映射到集合

{0,

1,…,

n-1}，在这个集合上的算术运算称为

模运算，模运算有以下性质：①[(amodn)+(bmodn)]modn

=

(a+b)modn②[(amodn)-(bmodn)]modn

=

(a-b)modn③[(amodn)×(bmodn)]modn

=

(a×b)modn数论基础模运算性质①的证明：设

(amodn)=

ra，(bmodn)

=

rb，则存在整数

j、k

使得

a

=

jn+ra，b

=

kn+rb，因此：(a+b)modn

=

[(j+k)n+ra+rb]modn

=

(ra+rb)modn

=[(amodn)+(bmodn)]modn（证毕）性质②、③的证明类似。数论基础模运算例：设

Z8

=

{0,

1,

…,

7}，考虑

Z8

上的模加法和模乘法，结果如下表所示：+801234567001234567112345670223456701334567012445670123556701234667012345770123456×801234567000000000101234567202460246303614725404040404505274163606420642707654321数论基础模运算例：设

Z8

=

{0,

1,

…,7}，考虑

Z8

上的模加法和模乘法，结果如下表所示：从加法结果可见，对每一

x，都有一

y，使得x+y≡0mod8。称y为x的负数，也称为加法逆元。对

x，若有

y，使得

x×y≡1mod8，如

3×3≡1mod8，则称

y

为

x

的倒数，也称为

乘法逆元。在本例中并非每一

x

都有乘法逆元。数论基础模运算一般地，定义

Zn

为小于

n

的所有非负整数集合，即

Zn

=

{0,

1,…,

n-1}，称

Zn

为模

n

的同余类。其上的模运算有以下性质：①交换律：(w+x)modn

=

(x+w)modn

(w×x)modn

=

(x×w)modn②结合律：[(w+x)+y]modn

=

[w+(x+y)]modn

[(w×x)×y]modn

=

[w×(x×y)]modn数论基础模运算一般地，定义

Zn

为小于

n

的所有非负整数集合，即

Zn

=

{0,

1,…,

n-1}，称

Zn

为模

n

的同余类。其上的模运算有以下性质：③分配律：[w×(x+y)]modn

=

[w×x+w×y]modn④单位元：(0+w)modn

=

wmodn

(1×w)modn

=

wmodn⑤加法逆元：对

w∈Zn，存在

z∈Zn，使得

w+z≡0modn，记

z

=

-w。数论基础模运算一般地，定义

Zn

为小于

n

的所有非负整数集合，即

Zn

=

{0,

1,…,

n-1}，称

Zn

为模

n

的同余类。此外还有以下性质：加法可约律：如果

(a+b)≡(a+c)modn，

则

b≡cmodn该性质可由

(a+b)≡(a+c)modn

的两边同加上

a

的加法逆元得到。类似性质对乘法却不一定成立。仔细观察可见，与

8

互素的几个数

1，3，5，7

都有乘法逆元。这几个数有什么特点呢？这一结论可推广到任一

Zn。数论基础模运算定理：设

a∈Zn，gcd(a,n)

=

1，则

a

在

Zn

中有乘法逆元。证明：首先，集合a

×

Zn={0,a,2a,…,(n-1)a}(modn)

与集合Zn

等价：

<n;

ia

modn

≠jamodn,iffi≠j,

i,j

∈Zn然后，存在x

∈Zn，满足ax

≡1modn数论基础模运算(小结)加法：

a+bmodn=(amodn)+(bmodn)modn

减法：

a-bmodn=a+(-b)modn乘法，重复加法：

a×bmodn=(amodn)×(bmodn)modn

除法：（乘法约简律）

a/bmodn

=a×b-1modn注意：b-1是

bmodn的乘法逆元，存在的条件是

gcd(b,n)

=1数论基础欧几里得(Euclid)算法数论中的一个基本技术：求两个正整数的最大公因子的简化方法。扩展Euclid算法不仅可以求出两个正整数的最大公因子，而且当两个正整数互素时，还可求出其中一个数关于另一个数的乘法逆元。数论基础欧几里得(Euclid)算法求最大公因子Euclid算法基于以下基本结论：

对任意非负整数a

和正整数b，有

gcd(a,b)=gcd(b,amodb)课堂练习题：证明上述命题。数论基础欧几里得(Euclid)算法求最大公因子Euclid(f,d)：

设算法的输入是两个非负整数f,d，并且

f>dEuclid(f,d){

X←f;Y←d；#: ifY=0thenreturnX=gcd(f,d)；

R=XmodY；

X=Y；

Y=R；

goto#;}欧几里得(Euclid)算法求最大公因子例子，gcd(1970,1066)1970=1x1066+904 gcd(1066,904)

1066=1x904+162 gcd(904,162)

904=5x162+94 gcd(162,94)

162=1x94+68 gcd(94,68)

94=1x68+26 gcd(68,26)

68=2x26+16 gcd(26,16)

26=1x16+10 gcd(16,10)

16=1x10+6 gcd(10,6)

10=1x6+4 gcd(6,4)

6=1x4+2 gcd(4,2)

4=2x2+0 gcd(2,0)数论基础欧几里得(Euclid)算法求乘法逆元如果gcd(a,b)=1，则b

在moda下有乘法逆元（不妨设b<a），即存在x(x<a)，使得bx≡1moda。扩展Euclid算法可求出gcd(a,b)，当gcd(a,b)=1，还得到b

的逆元。数论基础ExEuclid(f,d){//设f>d

(X1,X2,X3)←(1,0,f);(Y1,Y2,Y3)←(0,1,d);#:ifY3=0thenreturnX3=gcd(f,d)；noinverse;ifY3=1thenreturnY3=gcd(f,d)；Y2=d-1modf;Q=X3/Y3

；

(T1,T2,T3)←(X1-QY1,X2-QY2,X3-QY3);(X1,X2,X3)←(Y1,Y2,Y3);(Y1,Y2,Y3)←(T1,T2,T3);goto#;}fX1