百草枯中毒

现代密码学中的数论基础知识梳理导读数论是⼀门研究⾃然数之间的关系和规律的学科，普遍认为是纯数学的分⽀，但并⾮是完全没有实⽤性的学科。现代密码学中⽤到了很多基础数论中的结论，特别是公钥加密体系（例如RSA算法，椭圆曲线加密等）。本⽂⽬的在于梳理现代密码学中常⽤到的基础数论⽅⾯的定理和结论。其中包括素数的特性、欧⼏⾥德算法、线性⽅程定理、算术基本定理、模算数运算、线性同余定理、欧拉函数、费马⼩定理、中国剩余定理、欧拉定理、本原根、离散对数问等等⼀些基础知识。了解这些知识，应该能够理解现代密码学中经典的Diffie-Hellman密钥协商和RSA算法的原理，进⽽能够理解秘钥管理、数字签名、消息认证、公钥证书等密码学领域的问题。本⽂很⼤程度上参考了数论概述⾥⾯的内容，也借鉴了算法导论和密码编码学与⽹络安全原理与实践的相关章节。⼀、关于互质和整除的⼀些有⽤结论和定理数论对素数的特性尤其感兴趣，素数是整数的基础构件，就像是元素在化学式中的作⽤类似。1、dd整除aa记作：d∣ad∣a如果d∣ad∣a且d∣bd∣b，那么d∣(ax+by)d∣(ax+by).2、如果pp是素数，且pp整除乘积abab，则pp整除aa或者pp整除bb（或者pp同时整除aa和bb）。证明的关键是假设pp不整除aa，考虑1=gcd(p,a)1=gcd(p,a)同时整除pp和aa。但由于pp是素数，pp的因⼦只能是1或者pp，所以gcd(p,a)=1gcd(p,a)=1。由后⾯的线性⽅程定理得知，可以构造线性⽅程px+ay=1=gcd(p,a)px+ay=1=gcd(p,a)，两边同时乘上bb，得bpx+aby=bbpx+aby=b，pp整除左边等价于pp整除右边的bb。pp不整除bb的情况可以⽤同样的⽅式证明。拓展：如果素数pp整除整数乘积a1a2a3...ara1a2a3...ar,则p⾄少整除a1a1,a2a2,a2a2,......,arar中⾄少⼀个因数。3、1和任意⼀个⾃然数是都是互质关系。4、任意两个质数构成互质关系。5、⼀个数是质数，另⼀个数只要不是前者的倍数，两者就构成互质关系，⽐如3和10。6、如果两个数之中，较⼤的那个数是质数，则两者构成互质关系，⽐如97和57。7、pp是⼤于1的整数，则pp和p−1p−1构成互质关系，⽐如57和56。8、pp是⼤于1的奇数，则pp和p−2p−2构成互质关系，⽐如17和15。9、素数pp与1到p−1p−1的任意整数均互质。并且阶乘(p−1)!(p−1)!与pp互质，这个结论在后⾯费马⼩定理和欧拉定理的证明过程中会⽤到。⼆、欧⼏⾥德算法欧⼏⾥德算法的原理和流程其实⽐较容易理解。(GCD递归定理)：对于任意的⾮负整数aa和正整数bb，满⾜gcd(a,b)=gcd(b,amodb)gcd(a,b)=gcd(b,amodb)更详细的将，其计算流程：a=q1×b+r1b=q2×r1+r2r1=q3×r2+r3r2=q4×r3+r4...rn−3=qn−1×rn−2+rn−1rn−2=qn×rn−1+rnrn−1=qn+1×rn+0a=q1×b+rrnrn即为求得的aa和bb的最⼤公约数。以上流程主要需要思考三个问题：1）为什么rnrn是公约数？（需要从下往上推理）2）为什么rnrn是最⼤的公约数？（假设dd是aa与bb的任意公约数，如果能够证明dd整数rnrn，即可得证。）3）为什么欧⼏⾥德算法最后⼀定会终⽌？（因为每轮辗转之后的余数是单调递减的，辗转的轮次数有上界，最后⼀定能够保证余数为0，然后取最后⼀个⾮零余数rnrn就是正确的结果。）算法实现Demo：//欧⼏⾥德算法迭代实现publicstaticintgetGCD(inta,intb){if(a=breturngetGCD(b,a);}if(b>=1){//保证b>=1inttemp=0;while(b>0){temp=a%b;a=b;b=temp;}returna;}else{return-1;}}三、扩展欧⼏⾥德算法扩展欧⼏⾥德算法可以⽤来求解⼀类有意思的线性⽅程的整数解，该线性⽅程的整数求解过程与最⼤公约数有密切关系。对于线性⽅程（a,b,ca,b,c为常数）：ax+by=cax+by=c是很熟悉的⽅程。这⾥讨论情况是a,b,ca,b,c满⾜⼀定的关系：c=gcd(a,b)c=gcd(a,b)，也即是这样的线性⽅程：ax+by=gcd(a,b)ax+by=gcd(a,b)这个线性⽅程必然有整数解，但我们更关⼼如果⽤更好算法去求解，该算法利⽤欧⼏⾥德算法求解最⼤公约数过程中的中间商和余数，进⾏扩展运算，在求gcd(a,b)gcd(a,b)的过程中，同时也就求得线性⽅程的整数解(x,y)(x,y)。算法实现Demo：publicstaticlong[]gcdExt(longa,longb){longans;long[]result=newlong[3];if(b==0){result[0]=a;result[1]=1;result[2]=0;returnresult;}long[]temp=gcdExt(b,a%b);ans=temp[0];result[0]=ans;result[1]=temp[2];result[2]=temp[1]-(a/b)*temp[2];returnresult;}四、算术基本定理(算术基本定理)：每个整数n⩾2n⩾2可唯⼀分解成素数的乘积：n=pe11pe22...perrn=p1e1p2e2...prer其中，pipi为素数，且p1设计

领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计