第8章+数论入门

第8章数论入门本章内容素数模运算Euclid算法费马定理和欧拉定理素性测试中国剩余定理离散对数费尔马定理和欧拉定理•费尔马（Fermat）定理：若p是素数，a是正整数且gcd(a,p)=1，则ap-1≡1modp。•证明：考虑集合{1,2,…,p-1},对每个数乘以a,得到集合{amodp,2amodp,…,(p-1)amodp},两两不同且都在1与p-1之间,因此两个集合相同:{amodp,2amodp,…,(p-1)amodp}={1,2,…,p-1}所以：(p-1)!modp=1×2×…×(p-1)≡a×2a×…×(p-1)a≡[(amodp)×(2amodp)×…×((p-1)amodp)]modp≡[(p-1)!ap-1]modp由于(p-1)!与p互素，因此(p-1)!有乘法逆元，由乘法可约律得ap-1≡1mod•推论：设p是素数，a是任一正整数，则ap≡amodp欧拉函数•设n是一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为φ(n)。例如：φ(6)=2，φ(7)=6，φ(8)=4。•若n是素数，则显然有φ(n)=n-1。•定理：若n是两个互异的素数p和q的乘积，则φ(n)=φ(p)×φ(q)=(p-1)×(q-1)例如：由21=3×7，得φ(21)=φ(3)×φ(7)=2×6=12定理假定,1nieiipm这里ip均为素数且互不相同，niei1,0。则：nieieiiippm11)()(.若,mpqp、q是素数,则)1)(1()(qpm回顾欧拉函数的求值公式若n是两个互异的素数p和q的乘积，则φ(n)=φ(p)×φ(q)=(p-1)×(q-1)费尔马定理和欧拉定理•欧拉（Euler）定理：若a和n互素，则aφ(n)≡1(modn)；•证明:R={x1,x2,…,xφ(n)}为所有小于n且与n互素的正整数,考虑集合:S={(ax1modn),(ax2modn),…,(axφ(n)modn)}①(aximodn)与n互素②(aximodn)两两不等:•(aximodn)=(axjmodn)⇒ximodn=xjmodn③S有φ(n)个元素故S也是所有小于n且与n互素的正整数,因此S=R,从而：Πxi=Π(aximodn)≡(Π(axi))modn≡(aφ(n)Πxi)modn注意到xi与n互素,从而得到结论.•欧拉（Euler）定理推论：aφ(n)+1≡a(modn)若n=pq,p≠q都是素数,k是任意整数,则：mk(p-1)(q-1)+1≡mmodn,对任意0≤m≤n素性检验素性检验是指对给定的数检验其是否为素数直接判断一个整数是否为素数是困难的；对于大数的素性检验来说没有简单直接的方法，目前常用的是概率检验法，如Miller-Rabin算法素数分布密度：在n附近平均每隔(lnn)个整数就有一个素数。这样在找到一个素数之前，平均要测试大约lnn个整数。由于每个偶数会被立刻拒绝，所以实际上只需测试大约0.5lnn个整数。素性检验引理:如果p为大于2的素数，则方程x2≡1(modp)的解只有x≡1和x≡-1。证明：由x2≡1modp，有x2-1≡0modp，(x+1)(x-1)≡0modp，因此p|(x+1)或p|(x-1)或p|(x+1)且p|(x-1)。若p|(x+1)且p|(x-1)，则存在两个整数k和j，使得x+1=kp，x-1=jp,两式相减得2=(k-j)p，为不可能结果。所以有p|(x+1)或p|(x-1)。设p|(x+1)，则x+1=kp，因此x≡-1(modp)。类似地可得x≡1(modp)。（证毕）引理的逆否命题为：如果方程x2≡1modp有一解x0不为{-1,1}中的元素，那么p不为素数。例如：考虑方程x2≡1(mod8)，由Z8上模乘法的结果得12≡1mod8,32≡1mod8,52≡1mod8,72≡1mod8又5≡-3mod8，7≡-1mod8，所以方程的解为1，-1，3，-3，可见8不是素数。素性检验qka12qja12qja12素性检验目前还没有一个高效的办法，实际中应用最多Miller-Rabin算法《孙子算经》“物不知数”问题：“今有物，不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”求解方法：三人同性七十稀，五树梅花廿一只，七子团圆正半月，除百零五便得知。123702115105NRRRP南宋数学家秦九韶在他的《数书九章》中提出了“大衍求一术”，系统论述了一次同余式组求解程序。与19世纪高斯《算术探究》中关于一次同余式组的解法完全一致。中国剩余定理（CRT）设m1,m2,…,mk是两两互素的正整数，1kiiMm，则一次同余方程组1122modmodmodkkamxamxamx对模M有惟一解:112212modkkkMMMxeaeaeaMmmm其中ei满足1mod1,2,,iiiMemikm中国剩余定理（CRT）.........证明：设1,1,2,,kililliMMmikm由Mi的定义得Mi与mi是互素的，可知Mi在模mi下有惟一的乘法逆元，即满足1modiiiMemm的ei是惟一的。中国剩余定理（CRT）...下面证明对{1,2,,}ik，上述x满足(mod)iiamx。注意到当j≠i时，mi|Mj，即Mj≡0(modmi)。所以(Mj×ejmodmj)modmi≡((Mjmodmi)×((ejmodmj)modmi))modmi≡0而(Mi×(eimodmi))modmi≡(Mi×ei)modmi≡1所以x(modmi)≡ai，即ai(modmi)≡x中国剩余定理（CRT）...下面证明方程组的解是惟一的。设'x是方程组的另一解，即'(mod)(1,2,,)iixamik由(mod)iixam得'0(mod)ixxm，即|(')imxx。再根据mi两两互素，有|(')Mxx，即'0(mod)xxM，所以'(mod)(mod)xMxM。(证毕)中国剩余定理（CRT）...例：由以下方程组求x。1mod22mod33mod55mod7xxxx解：M=2·3·5·7=210，M1=105，M2=70，M3=42，M4=30,易求111mod21eM,122mod31eM,133mod53eM,144mod74eM,所以xmod210≡(105×1×1+70×1×2+42×3×3+30×4×5)mod210≡173，或写成x≡173mod210。中国剩余定理（CRT）中国剩余定理是数论中最有用的一个工具，定理说如果已知某个数关于一些两两互素的数的同余类集，就可重构这个数。例如：Z10中每个数都可从这个数关于2和5（10的两个互素的因子）的同余类重构。比如已知x关于2和5的同余类分别是[0]和[3]，即xmod2≡0，xmod5≡3。可知是偶数且被5除后余数是3，所以可得8是满足这一关系的惟一的x。中国剩余定理（CRT）中国剩余定理提供了一个非常有用的特性，即在模M下可将非常大的数x由一组小数(a1,a2,…,ak)表达。例：将973mod1813由模数分别为37和49的两个数表示。解：取x=973,M=1813,m1=37,m2=49。由a1≡973modm1≡11,a2≡973modm2≡42得x在模37和模49下的表达为（11,42）。此性质使得模M的大数运算转化到更小的数上来进行运算，当M为150位或150位以上时，这种方法非常有效。中国剩余定理（CRT）Euler定理指出如果gcd(a,n)=1，则()1modnan。现在考虑如下的一般形式:1modman如果a与n互素，则至少有一整数m（比如()mn）满足这一方程。称满足方程的最小正整数m为模n下a的阶。离散对数求模下的整数幂例如：a=7，n=19，则易求出71≡7mod19,72≡11mod19,73≡1mod19，即7在模19下的阶为3。由于73+j=73·7j≡7jmod19,所以74≡7mod19,75≡72mod19,…,即从74mod19开始所求的幂出现循环，循环周期为3，即循环周期等于元素的阶。离散对数定理:设a的阶为m，则ak≡1modn的充要条件是k为m的倍数。推论：a的阶m整除φ(n)。如果a的阶m等于φ(n)，则称a为n的本原根。如果a是n的本原根，则23(),,,,naaaa在modn下互不相同且都与n互素。特别地，如果a是素数p的本原根，则231,,,,paaaa在modp下都不相同。离散对数......例如：n=9，则φ(n)=6，考虑2在mod9下的幂21mod9≡2,22mod9≡423mod9≡8,24mod9≡7，25mod9≡5,26mod9≡1。即2的阶为φ(9)，所以2为9的本原根。例如：n=19，a=3在mod19下的幂分别为3，9，8，5，15，7，2，6，18，16，10，11，14，4，12，17，13，1。即3的阶为18=φ(19)，所以3为19的本原根。离散对数本原根不惟一。可验证除3外，19的本原根还有2，10，13，14，15。注意并非所有的整数都有本原根，只有以下形式的整数才有本原根：2,4,,2aapp其中p为奇素数。离散对数指标一般对数：指数函数y=ax(a0,a≠1)的逆函数称为以a为底x的对数，记为y=logax。对数函数有以下性质：loga1=0,logaa=1,logaxy=logax+logay,logaxy=ylogax在模运算中也有类似的函数。设p是一素数，a是p的本原根，则21,,,paaa产生出1到p-1之间的所有值，且每一值只出现一次。因此对任意b∈{1,2,…,p-1}，都存在惟一的i(1≤i≤p-1)，使得b≡aimodp。称i为模p下以a为底b的离散对数（指标），记为i=inda,p(b)。以上假定模数p是素数，对于非素数也是一样。离散对数性质：inda,p(1)=0inda,p(a)=1若az≡aqmodp，其中a和p互素，则有z≡qmodφ(p)inda,p(xy)=[inda,p(x)+inda,p(y)]modφ(p)inda,p(yr)=[r×inda,p(y)]modφ(p)从指标的以上性质可见，指标与对数的概念极为相似。离散对数离散对数的计算:YgXmodp–已知g,x,p,计算y是容易的–已知y,g,p,计算x是困难的离散对数目前已知的最快的求离散对数算法其时间复杂度为：2133explnlnlnOpp所以当p很大时，该算法也是不可行的。计算上的安全性•安全性的理论基础：复杂性理论•算法是求解某个问题的一系列具体步骤，通常可理解为求解某个问题的通用计算机程序。•问题是需要回答的一般性提问，通常含有若干个未定参数或自由变量。问题的描述包括–给定所有的未定参数的一般性描述–陈述“答案”或“解”必须满足的性质•一个算法的复杂性由该算法所需求的最大时间（T）和存储空间（S）度量。由于算法用于同一问题的不同规模实例所需求的时间和空间往往不同，所以总是将他们表示成问题实例的规模n的函数，n表示描述该实例所需的输入数据长度。算法复杂性•算法复杂性用“大O”的符号来表示，它表示算法复杂性的数量级。f(n)=O(g(n))意味着存在常数c和n0，使得对一切n≥n0,有f(n)≤c|g(n)|。•通常按时间（或空间）复杂性对算法进行分类。一个输入的大小为n的算法被称为是：–线性的：如果运行时间是O(n)–多项式的：如果运行时间是O(nt),其中t是一个常数–指数的：如果运行时间是O(th(n)),其中t是一个常数,h(n)是一个多项式•一般地，一个可以在多项式时间内解决的问题被认为是可解的，而任何比多项式时间更长的时间，尤其是指数时间，被认为是不可解的。