19初等数论 (1)

1、第19章初等数论,以整数集为典型代数系统的数论知识一直被认为是既神秘又古老。虽然绝大多数人自小学生起就开始认识它，而一些数学家却一辈子踏着它往皇冠上攀。现在，计算机终于给数论这门再纯洁不过的数学分支扬起了应用的帆。我们这里介绍的虽然只是初等数论的基础知识，但它们在计算机的数据表示、数据传输以及电子商务应用中的数据保密等方面起着非常重要的作用。,第19章初等数论,19.1素数19.2最大公约数与最小公倍数19.3同余19.4一次同余方程19.5欧拉定理和费马小定理19.6初等数论在计算机科学技术中的几个应用,19.1素数,整除、倍数和因子带余除法素数与合数算术基本定理筛法,整除、倍数和因子,今后

2、只考虑正整数的正因子.平凡因子:1和自身真因子:除1和自身之外的因子例如,2,3是6的真因子,设a,b是两个整数，且b0.如果存在整数c使a=bc，则称a被b整除，或b整除a，记作b|a.此时,又称a是b的倍数，b是a的因子.把b不整除a记作ba.例如,6有8个因子1,2,3和6.,整除的性质,性质19.1若a|b且a|c,则x,y,有a|xb+yc.性质19.2若a|b且b|c,则a|c.性质19.3设m0,则a|b当且仅当ma|mb.性质19.4若a|b且b|a,则a=b.性质19.5若a|b且b0,则|a|b|.,带余除法:a=qb+r,0r1,p是素数且d|p,则d=p.性质19.7设

3、p是素数且p|ab,则必有p|a或者p|b.设p是素数且p|a1a2ak,则必存在1ik,使得p|ai.性质19.8a1是合数当且仅当a=bc,其中1ba,1c1,则a=,其中p1,p2,pk是不相同的素数,r1,r2,rk是正整数,并且在不计顺序的情况下,该表示是惟一的.该表达式称作整数a的素因子分解.例如30=235,117=3213,1024=210推论设a=,其中p1,p2,pk是不相同的素数,r1,r2,rk是正整数,则正整数d为a的因子的充分必要条件是d=,其中0siri,i=1,2,k.,例题,例121560有多少个正因子?,解21560=2357211由推论,21560的正因子

4、的个数为4232=48.,例210!的二进制表示中从最低位数起有多少个连续的0?,解2,3,4=22,5,6=23,7,8=23,9=32,10=25.得10!=2834527,故10!的二进制表示中从最低位数起有8个连续的0.,素数的分布,梅森数(MarinMersenne):2p1,其中p为素数当n是合数时,2n1一定是合数,2ab1=(2a1)(2a(b1)+2a(b2)+2a+1).梅森数可能是素数,也可能是合数:221=3,231=7,251=31,271=127都是素数,而2111=2047=2389是合数.到2002年找到的最大梅森素数是2134669171,有4百万位.,定理1

5、9.2有无穷多个素数.证用反证法.假设只有有穷多个素数,设为p1,p2,pn,令m=p1p2pn+1.显然,pim,1in.因此,要么m本身是素数，要么存在大于pn的素数整除m,矛盾.,素数判定,1772年欧拉(瑞,1701-1783)证明第8个梅森素数M31,有10位数字.1996年美国数学家及程序设计师乔治沃特曼编制了因特网梅森素数大搜索程序(GIMPS项目),将其放置在因特网上供数学爱好者使用。目前有150多个国家的9万多名志愿者、超过25万台计算机参与这项计划.,该计划利用大量普通计算机的闲置时间,获得相当于超级计算机的运算能力，近年来新产生的梅森素数都是通过GIMPS项目找到的.美国

6、电子新领域基金会设立了10万美元的奖金,鼓励第一个找到超过千万位素数的人;25万美元奖第一个找到超过十亿位素数的人.,素数判定,在“手算笔录年代”仅找到12个梅森素数,近10多年来通过GIMPS项目找到了10个(35至44个)梅森素数.,德国眼科专家马丁诺瓦克2005年2月18日发现第42个梅森素数M25964951,有7816230位数.美国数学家库珀和化学家布恩,2005年12月15日发现第43个梅森素数M30402457,有9152052位数;他们在2006年9月4日又发现第44个梅森素数M32582657,有9808358位数,如果用普通字号将这个数字连续写下来,它的长度超过40公里.

7、周海中（中）梅森素数分布猜测（1992）,素数判定,素数的分布(续),(n):小于等于n的素数个数.例如(0)=(1)=0,(2)=1,(3)=(4)=2,(5)=3.,素数的分布(续),补充定理当n67时,定理19.3(素数定理),素数测试,定理19.4如果a是合数,则a必有小于等于的真因子.证由性质19.8,a=bc,其中1()2=a,矛盾.推论如果a是合数,则a必有小于等于的素因子.证由定理19.4,a有小于等于的真因子b.如果b是素数,则结论成立.如果b是合数,由性质19.9和性质19.5,b有素因子p0.一次同余方程的解:使方程成立的整数例如,2x0(mod4)的解为x0(mod2)

8、,2x1(mod4)无解,实例,例1解一次同余方程6x3(mod9).解gcd(6,9)=3|3,方程有解.取模9等价类的代表x=4,3,2,1,0,1,2,3,4,检查它们是否是方程的解,计算结果如下:6(4)6(1)623(mod9),6(3)60630(mod9),6(2)61646(mod9),得方程的解x=4,1,2(mod9),方程的最小正整数解是2.,模m逆,定理19.10(1)a的模m逆存在的充要条件是a与m互素.(2)设a与m互素,则在模m下a的模m逆是惟一的.证(1)这是定理11.9的直接推论.(2)设ab11(modm),ab21(modm).得a(b1b2)0(modm

9、).由a与m互素,b1b20(modm),得证b1b2(modm).,定义19.4如果ab1(modm),则称b是a的模m逆,记作a1(modm)或a1.a1(modm)是方程ax1(modm)的解.,实例,例2求5的模7逆.,解5与7互素,故5的模7逆存在.,方法1.解方程5x1(mod7).,检查x=3,2,1,0,1,2,3,得到513(mod7).,方法2.做辗转相除法,求得整数b,k使得5b+7k=1,则b是5的模7逆.,计算如下:7=5+2,5=22+1.回代1=522=52(75)=3527,得513(mod7).,实例,例2(续),方法3.直接观察,53=15,151(mod7

10、),得513(mod7).,11.5欧拉定理和费马小定理,欧拉函数欧拉定理费马小定理,欧拉(Eular)定理,欧拉函数(n):0,1,n1中与n互素的数的个数例如(1)=(2)=1,(3)=(4)=2.当n为素数时(n)=n1;当n为合数时(n)n1.定理19.11(欧拉定理)设a与n互素,则a(n)1(modn).,欧拉定理的证明,证设r1,r2,r(n)是0,1,n1中与n互素的(n)个数.由于a与n互素,对每一个1i(n),ari也与n互素,故存在1(i)(n)使得arir(i)(modn).是1,2,(n)上的映射.要证是一个单射.a的模n逆a1存在,a1也与n互素.假设ij,(i)=

11、(j),则有ariarj(modn).两边同乘a1,得rirj(modn),矛盾.得证是1,2,(n)上的单射,当然也是1,2,(n)上的双射.从而,有而与n互素,故a(n)1(modn).,费马(Fermat)小定理,定理19.12(费马小定理)设p是素数,a与p互素,则ap-11(modp).另一种形式是,设p是素数,则对任意的整数a,apa(modp).费马小定理提供了一种不用因子分解就能断定一个数是合数的新途径.例如,2914(mod9),可以断定9是合数.,19.6初等数论在计算机科学技术中的几个应用,19.6.1产生均匀伪随机数的方法随机数与伪随机数线性同余法与乘同余法,线性同余法

12、,随机数:随机变量的观察值伪随机数(0,1)上的均匀分布U(0,1):a(0a1),P0Xa=a线性同余法选择4个非负整数:模数m,乘数a,常数c和种子数x0,其中2am,0cm,0x0m,用递推公式产生伪随机数序列:xn=(axn1+c)modm,n=1,2,取un=xn/m,n=1,2,作为U(0,1)伪随机数.,线性同余法(续),线性同余法产生的序列的质量取决于m,a和c.例如m=8,a=3,c=1,x0=2,得到7,6,3,2,7,6,周期为4m=8,a=5,c=1,x0=2,得到3,0,1,6,7,4,5,2,3,0,1,周期为8.a=0,得到c,c,c,a=1,得到x0+c,x0+

13、2c,x0+3c,乘同余法:c=0(x00)的线性同余法,即xn=axn1modm,n=1,2,.最常用的均匀伪随机数发生器:m=2311,a=75的乘同余法,它的周期是2312.,19.6.11随机数的产生,现实世界充满不确定性，我们所研究的现实对象往往难以摆脱随机因素的影响要使我们的数学模型能够较真实地刻画实际对象，必须面对这个现实概率论是用数学的思想和方法处理和研究随机现象的一个有效的工具但是它还难以用来处理复杂系统中的随机性这里介绍使用计算机来模拟随机现象的方法，它经常应用于复杂系统的动态仿真的研究当中是处理复杂系统中随机性的计算机模型也是使用计算机研究和解决实际问题的一条重要途径,随

14、机现象的模拟,1均匀分布的随机数及其产生,对随机现象进行模拟，实质上是要给出随机变量的模拟也就是说利用计算机随机地产生一系列数值，它们的出现服从一定的概率分布,则称这些数值为随机数。最常用的是在(0,1)区间内均匀分布的随机数，也就是我们得到的这组数值可以看作是(0,l)区间内均匀分布的随机变量的一组独立的样本值以后我们将指出其它分布的随机数可利用均匀分布的随机数产生,随机现象的模拟,记XU(0,1),0,1)区间上均匀分布的随机变量X的概率密度f(x)和概率分布函数F(x)分别为:,数学期望:E(X)=1/2;方差:=1/12,随机现象的模拟,下图为均匀分布的密度函数和分布函数示意图：,随机

15、现象的模拟,均匀随机数是产生其它随机数的基础。例如，抛硬币、抽签、统计经验分布都可以由它产生。,产生随机数的方法：,（1）随机数表:1927年,4万随机数表,以后有100万随机数表（可以输入内存，随时调用）；,（2）硬件设备：从真实物理现象的随机因素中产生随机数，放射性粒子的放射源，电子晶体管的固有噪音等，单位时间内放射出的粒子数是随机的。优点：真正的随机数；缺点：外部设备，无法重复,随机现象的模拟,（3）数学公式：产生伪随机数用数学公式或位移寄存器的移位操作来产生的随机数,称为伪随机数.因为真实的随机数,只能从客观真实的随机现象本身产生出来,所以产生理想的伪随机数列不是一件容易的事.,一般对

16、于产生伪随机数的方法,有如下几点要求:1)要求伪随机数列有较理想的随机性和均匀性,就是对其随机性和均匀性进行统计检验时,有合乎要求的精度;2)产生伪随机数的程序应当简短、运算速度快,占用计算机的内存单元少;3)伪随机数列的循环周期应当尽可能地大,以满足模拟的需要4)伪随机数列中,前后之间和各子列之间,要求相互是独立无关的。,随机现象的模拟,当我们需要一系列均匀分布的随机数时,可以按照一定的算法由计算机计算产生的伪随机数产生随机数的方法很多，其中以乘同余法使用较广用以产生均匀分布随机数的乘同余法的递推公式为：,xn+1=xn(modM),rn=xn/M,其中，是乘因子，M是模数前面式子的右端称为

17、以M为模数（modulus）的同余式。给定了一个初值x0(称为种子)后，计算出的rn即为(0,l)上均匀分布的随机数,随机现象的模拟,无论用哪一种方法产生的随机数都存在这样的问题，必须对它进行统计检验看看它们是否具有较好的独立性和均匀性一般在计算机(或计算器)及其使用的算法语言中都有随机数生成的命令，它们所生成的随机数都是经过检验并且可用的.这里就不再详细介绍检验的方法了,C语言中与随机数有关的函数：randomize(void);初始化x=random(intM);产生0M之间的随机数x=rand(void);产生0215-1之间的随机数,随机现象的模拟,C语言中与随机数有关的函数：rand

18、omize(void);初始化x=random(intM);产生0M之间的随机数x=rand(void);产生0215-1之间的随机数Matlab中与随机数有关的函数：Rand(n)n个0,1之间均匀分布随机数Rand(m,n)m*n个0,1之间均匀分布随机数randn(n)n个N(0,1)标准正态分布随机数randn(m,n)m*n个N(0,1)标准正态分布随机数,随机现象的模拟,2随机变量的模拟,利用均匀分布的随机数可以产生具有任意分布的随机变量的样本，从而可以对随机变量的取值情况进行模拟,（l）离散型随机变量的模拟设随机变量X的分布律为Pr(X=xi)=pi,i=1,2,令p(0)=0,

19、p(n)=pi,n=1,2,将p(n)作为分点，把区间(0,1)分为一系列小区间(p(n-1),p(n)对于均匀的随机变量RU(0,l)，则有,Pr(p(n-1)Rp(n)=p(n)-p(n-1)=pi,n=1,2,n,i=1,随机现象的模拟,由此可知，事件(p(n-1)Rp(n)和事件(X=xn)有相同的发生的概率因此我们可以用随机变量R落在小区间内的情况来模拟离散的随机变量X的取值情况具体执行的过程是：每产生一个(0,1)上均匀分布的随机数（以后简称随机数）r，若p(n-1)rp(n)则理解为发生事件“X=xn”于是就可以模拟随机变量的取值情况,随机现象的模拟,（2）连续型随机变量的模拟,

20、一般说来，具有给定分布的连续型随机变量可以利用在区间（0，1）上均匀分布的随机数来模拟最常用的方法是反函数法,由概率论的理论可以证明，若随机变量Y有连续的分布函数F(y)，而X是区间（0，l）上均匀分布的随机变量，令ZF-1(X)，则Z与Y有相同的分布由此，若已知Y的概率密度为f(y)，由Y=F-1(X)可得,XF(Y)=f(y)dy,Y,-,随机现象的模拟,是区间（0，l）上均匀分布的随机变量如果给定区间（0，1）上均匀分布的随机数ri，则具有给定分布的随机数yi可由方程中解出,riF(Y)=f(y)dy,yi,0,例当需要模拟服从参数为的指数分布时,由,rie-xdy=1-e-yi,yi,

21、0,可得yi=-(1/)ln(1-ri).因为(1-ri)和ri同为(0，1)区间上的均匀分布的随机数，故上式可以简化为yi=-(lnri)/.,随机现象的模拟,反函数法是一种普通的方法，但当反函数不存在或难以求出时，就不宜于使用了舍选法是另一种方法，其实质是从许多均匀随机数中选出一部分，使之成为具有给定分布的随机数步骤如下：,设随机变量X有密度f(x)，又存在实数ab，使Pr(aXb)=1.,1).选取常数，使f(x)l，x(a,b);,2).产生均匀的随机数r1和r2，令y=a(b-a)r1；,随机现象的模拟,3).若r2f(y)，则令x=y，否则剔除r1和r2，重返步骤2，如此重复循环，

22、产生的随机数x1,x1,.,xn,服从的概率分布由密度函数f(x)确定,若不存在上述的有限区间，可以选择一个有限区间(a1,b1)使得Pr(a11-其中是充分小的正数重复上面的步骤，所产生的随机数仅会出现较小的误差,随机现象的模拟,（3）正态随机数的模拟,除了可用反函数和舍选法模拟正态随机变量外,还有两种常用的方法,坐标变换法:设r1,r2是相互独立的均匀随机数,令x1(-2lnr1)1/2cos(2r2)x2=(-2lnr1)1/2sin(2r2)则x1,x2是相互独立的标准正态的随机数,随机现象的模拟,另一个方法是利用中心极限定理设xi,i=1,2,n是n个相互独立的(0,1)上的均匀的随

23、机变量，有E(xi)=1/2,D(xi)=1/12，由中心极限定理知y=(xi-)将渐近服从正态分布N(0,l)因此，取n个均匀的随机数ri,则有y=(ri-),n/12,l,i=1,n,n,2,n/12,l,i=1,n,n,2,随机现象的模拟,将可看成是标准正态分布N(0,1)的随机数这里的n应取得足够大，一般取n=10即可若取n=12,则上式简化为z=ri-6再由y=x+得到正态分布N(,2)的随机数y.,i=1,n,计算机仿真举例,例1.4赶火车过程仿真一列火车从A站经过B站开往C站，某人每天赶往B站乘这趟火车。已知火车从A站到B站运行时间为均值30分钟、标准差为2分钟的正态随机变量.火

24、车大约在下午1点离开A站。离开时刻的频率分布为,计算机仿真举例,用计算机仿真火车开出、火车到达B站、这个人到达B站情况，并给出能赶上火车的仿真结果。,引入以下变量：T1火车从A站开出的时刻；T2火车从A站运行到B站所需要的时间；T3此人到达B站的时刻；,这个人到达B站时的频率分布为：,计算机仿真举例,T1,T2,T3是随机变量，其概率分布为x=0.7,x2=0.9,y1=0.3,y2=0.7,y3=0.9,开车时间的仿真测试s1=0;s2=0;s3=0;x=rand(10000,1);fori=1:10000ifx(i)0.9s3=s3+1;endends1/10000,1-s1/10000-

25、s3/10000,s3/10000,计算机仿真举例,s1=0;s2=0;s3=0;s4=0;x=rand(10000,1);fori=1:10000ifx(i)0.3s1=s1+1;elseifx(i)0.7s2=s2+1;elseifx(i)0.9s3=s3+1;elses4=s4+1;endendends1/10000,s2/10000,s3/10000,s4/10000,人到达时刻仿真测试,计算机仿真举例,火车运行时间的仿真测试x=randn(10000,1);fori=1:10000y(i)=30+2*x(i);end,赶上火车的仿真结果s=0;x1=rand(10000,1);x2=

26、rand(10000,1);x3=randn(10000,1);fori=1:10000ifx1(i)0.7T1=0;elseifx1(i)0.9T1=5;elseT1=10;endT2=30+2*x3(i);,ifx2(i)0.3T3=28;elseifx2(i)0.7T3=30;elseifx2(i)0.9T3=32;elseT3=34;endendifT3T1+T2s=s+1;endends/10000,19.6.2密码学,19.6.1恺撒密码明文,密文,加密,解密,密钥19.6.2RSA公钥密码私钥密码与公钥密码,密码学是研究信息隐藏的科学，一开始主要用于军事目的，两次世界大战期间，都

27、起到了关键的作用。现在由于计算机广泛应用于商业目的，信息安全是电子商务的关键核心，而密码学是信息和网络安全的核心。同余理论可以用于非常简单的信息保密目的。比如一个英文字母可以用另一个英文字母来代替，如最早的Caesar加密技术,恺撒(Caesar)密码,加密方法:ABCDEFGHIJKLMNOPQRSTUVWXYZDEFGHIJKLMNOPQRSTUVWXYZABC明文:SEEYOUTOMORROW密文:VHHBRXWRPRUURZ184424142019141214171714222177117232217151720201725加密算法E(i)=(i+k)mod26,i=0,1,25,解密

28、算法D(i)=(ik)mod26,i=0,1,25其中密钥k是一取定的整数,这里取k=3.,加密算法,线性同余加密算法E(i)=(ai+b)mod26,i=0,1,25,其中a与26互素.维吉利亚(Vigenere)密码把明文分成若干段,每一段有n个数字,密钥k=k1k2kn,加密算法E(i1i2in)=c1c2cn,其中cj=(ij+kj)mod26,ij=0,1,25,j=1,2,n.,RSA公钥密码,私钥密码:加密密钥和解密密钥都必须严格保密公钥密码(W.Diffie,M.Hellman,1976):加密密钥公开,解密密钥保密RSA公钥密码(R.Rivest,A.Shamir,L.Adleeman,1978)取2个大素数p和q(pq),记n=pq,(n)=(p1)(q1).选择正整数w,w与(n)互素,设d=w1(mod(n).将明文数字化,分成若干段,每一个明文段mn