《数论算法》教案-5章(原根与离散对数)

《数论算法》第五章原根与离散对数1/58第5章原根与离散对数内容1.整数的阶2.原根3.有原根的整数4.离散对数（指标）要点1.原根及其意义2.有原根的整数的条件3.离散对数及其性质5.1阶及其基本性质准备知识：（1）欧拉定理：m＞1，(a,m)＝1，则ma≡1（modm）（2）问题：①m是否是使得上式成立的最小正整数？②该最小正整数有何性质？(一)阶和原根概念【定义5.1.1】设m＞1，(a,m)＝1，则使得ea≡1（modm）成立的最小正整数e叫做a对模m的阶（或指数），记作mord(a)。若a的阶e＝m，则a叫做模m的原根。(二)应用：Diffie—Hellman密钥交换算法公钥算法的核心：（1）仅依赖公开信息不足以对算法构成威胁；（2）掌握私钥者可轻易获得信内容。《数论算法》第五章原根与离散对数2/58全局公开量q素数q的原根（＜q）生成用户密钥用户A选择秘密的AXAX＜q计算公开的AYAY≡AX（modq）用户B选择秘密的BXBX＜q计算公开的BYBY≡BX（modq）………交换公开密钥A→B：AYB→A：BY生成公共密钥K用户A计算K≡AXBY（modq）用户B计算K≡BXAY（modq）说明：K≡AXBY≡BXAY≡BAXX（modq）例：素数q＝353，原根α＝3A选AX＝97，计算AY≡973≡40mod353B选BX＝233，计算BY≡2333≡248mod353A与B交换A计算密钥K≡97248≡160mod353B计算密钥K≡23340≡160mod353(三)用定义求阶和原根《数论算法》第五章原根与离散对数3/58【例1】（按定义求阶和原根）m＝7，则(7)＝6。且11≡1，32≡1，63≡1，34≡1，65≡1，26≡1（mod7）故对模数7而言，1，2，3，4，5，6的阶分别为1，3，6，3，6，2。列表表示为a123456mord(a)136362因此，3，5是模7的原根。【例2】（快速求阶）m＝14＝2·7，(14)＝6，则11≡1，33≡－1，35≡－1，39≡1，311≡1，213≡1（mod7）列表a13591113mord(a)166332故3，5是模14的原根。【例3】（无原根的整数）m＝15＝3·5，(15)＝8，则a12478111314mord(a)14244242故模数15没有原根。同理，可知模数m＝9时，其原根为2，5；而整数8则没有原根。也可以计算验证5是模3、6、9、18的原根。《数论算法》第五章原根与离散对数4/58(四)阶的性质【定理5.1.1】设m＞1，(a,m)＝1，d为正整数，则da≡1（modm）mord(a)│d即d≡0（modmord(a)）（证）充分性：设mord(a)│d，则d＝k·mord(a)，从而da≡aordkma≡kaordma≡1（modm）必要性：反证：若da≡1且mord(a)d，则由欧几里得除法，有d≡mord(a)·q＋r，0＜r＜mord(a)从而ra≡raqaordma≡da≡1（modm）与mord(a)的最小性矛盾。【推论1】mord(a)│(m)。意义：mord(a)必是(m)的因子，故求mord(a)只需计算ia，其中i│(m)。【例4】（用定理5.1.1结论快速求阶及原根）（例7）求17ord(5)的值。（解）(17)＝16，只需计算d5（mod17），其中d＝1，2，4，8，16（实际上165不必计算）。15≡5，25≡8，45≡13≡－4，85≡16≡－1（mod17）《数论算法》第五章原根与离散对数5/58所以，17ord(5)＝16，即5是模17的原根。【例5】求33ord(4)、33ord(5)、33ord(7)的值。（解）(33)＝20。只需计算i4、i5、i7（mod33）（i＝1,2,4,5,10）。54≡1（mod33）；55≡23（mod33），105≡1（mod33）；57≡10（mod33），107≡1（mod33）∴33ord(4)＝5，33ord(5)＝10，33ord(7)＝10【推论2】设p是奇素数，21p也是奇素数，pa，则（1）若a是模p的二次剩余，则a不是p的原根，且当a≡1（modp）时，pord(a)＝1；当a1（modp）时，pord(a)＝21p；（2）若a是模p二次非剩余，则当a≡p－1（modp）时，pord(a)＝2；当ap－1（modp）时，pord(a)＝p－1。（3）此时，p有21p－1＝23p个原根。（4）当21p＝2为偶素数时，必有p＝5，其平方剩余为1和－1≡4，平方非剩余为2和3，且2和3是原根。（证）由推论1，pord(a)│(p)＝p－1＝2·21p，故pord(a)可能为1,2,21p,p－1。《数论算法》第五章原根与离散对数6/58（1）a是模p二次剩余，则由二次剩余的充分必要条件知21pa≡1（modp）由定理5.1.1知pord(a)│21p，但21p是素数，故pord(a)＝1或21p而pord(a)＝1a≡1（modp），故结论成立。（2）a是模p的二次非剩余，则由二次剩余的充分必要条件知21pa≡－1（modp）即pord(a)≠21p，那么，只有pord(a)＝2或p－1（pord(a)也不能为1，因为只有pord(1)＝1，但1是平方剩余，不是非剩余）而pord(a)＝2a≡p－1≡－1（modp），故结论成立。（3）由第4章结论知，p有21p个平方非剩余，其中只有pord(p－1)＝2，其余的pord(a)＝p－1，即原根有21p－1＝23p个。（4）显然。【例6】取p＝11，验证推论2。（解）首先，直接计算知：1，3，4，5，9是11的二次剩余，2，6，7，8，10是模11的二次非剩余。且有《数论算法》第五章原根与离散对数7/5811ord(1)＝1，11ord(3)＝11ord(4)＝11ord(5)＝11ord(9)＝5，11ord(2)＝11ord(6)＝11ord(7)＝11ord(8)＝10，11ord(10)＝2【性质1】设(a,m)＝1。（1）若b≡a（modm），则mord(b)＝mord(a)。（2）1ordam＝mord(a)。（证）（1）已知b≡a（modm），所以aordmb≡aordma≡1（modm）所以mord(b)│mord(a)。其次，bordma≡bordmb≡1（modm）所以mord(a)│mord(b)。∴mord(b)＝mord(a)（2）证法一：由aord1ma≡1aordma≡1（modm）知mord(1a)│mord(a);由a1a≡1（modm）知1aord1aam≡1（modm），即1aordam1aord1am≡1（modm），从而1aordam≡1（modm），所以mord(a)│mord(1a)。证法二：因为ka≡1（modm）的充分必要条件是k1a≡1（modm）【例7】已知整数39模17的阶为17ord(39)＝17ord(5)＝16。《数论算法》第五章原根与离散对数8/58则由此可知，整数7模17的阶为16，因为17≡5（mod17）。【定理5.1.2】设m＞1，(a,m)＝1，则1＝0a，a，2a，…，1aordma模m两两不同余。特别，若a是模m的原根，则上述(m)个数构成模m的简化剩余系。（证）反证法。若存在整数k，l（0≤l＜k＜mord(a)）使得ka≡la（modm）则由(a,m)＝1知lka≡1（modm）但0＜k－l＜mord(a)，与mord(a)的最小性矛盾。再设a是模m的原根，即mord(a)＝(m)，则1＝0a，a，2a，…，1ma模m两两不同余。由简化剩余系的等价条件知，上述(m)个数构成模m的简化剩余系。【例8】整数{k5│k＝0,1,2,…,15}组成模17的简化剩余系。（解）直接计算得k0123456789101112131415k515861314210161291143157【例9】设模数m＝18，选整数a＝5和7，验证定理5.1.2《数论算法》第五章原根与离散对数9/58的结论。（解）(18)＝6，直接计算得k012345k0123k5157171311k717131即{k5│k＝0,1,2,…,5}模18两两不同余，{k7│k＝0,1,2}模18两两不同余。且知5是模18的原根，从而{k5│k＝0,1,2,…,5}组成模18的简化剩余系。【定理5.1.3】设m＞1，(a,m)＝1，则da≡ka（modm）d≡k（modmord(a)）（证）首先d＝mord(a)q＋r，0≤r＜mord(a)，q≥0k＝mord(a)q＋r，0≤r＜mord(a)，q≥0又aordma≡1（modm），故da≡rqaordaam≡ra，ka≡ra（modm）必要性：已知da≡ka（modm）ra≡ra（modm）由定理5.1.2的证明过程知，r＝r，即d≡k（modmord(a)）（否则，设rr，则有rra≡1（modm），且r-r＜mord(a)，矛盾）充分性：若d≡k（modmord(a)），则d＝k＋mord(a)t∴da≡taordkmaa≡ka（modm）《数论算法》第五章原根与离散对数10/58【推论】na≡aordnmamod（modm）【例10】10000002≡102＝100（mod231），因为231ord(2)＝30，1000000≡10（mod30）。【例11】』因为7ord(2)＝3，所以20022≡3mod20022≡12＝2（mod7）。【定理5.1.4】（da的阶）设整数m＞1，(a,m)＝1，整数d≥0，则mord(da)＝daamm,ordord意义：（1）用a的阶求da的阶（2）若a为原根，可求出全部原根（3）求原根的个数（见定理5.1.5）（证）由定义5.1.1知dmaordda≡dmaordda≡1（modm）由定理5.1.1，mord(a)│dmord(da)，从而daamm,ordord│daamm,ordorddd＝dord,orddadamm但dadaammm,ordd,,ordord＝1，故《数论算法》第五章原根与离散对数11/58daamm,ordord│mord(da)另一方面，有d,aordaorddmma≡d,aorddaordmma≡1（modm）由定理5.1.1，mord(da)│daamm,ordord，所以daamm,ordord＝mord(da)【例12】已知17ord(5)＝16，25＝8（mod17），所以17ord(8)＝17ord(25)＝2,5ord5ord1717＝2,1616＝817ord(6)＝17ord(35)＝3,5ord5ord1717＝3,1616＝16【推论】设m＞1，g是模m的原根，整数d≥0，则dg是模m的原根(d,(m))＝1（证）由定理5.1.4，mord(dg)＝dggmm,ordord＝dmm,∴dg是原根dmm,＝(m)(d,(m))＝1【例13】由17ord(5)＝16可知5是模17的原根，由原根5就可以求出17的所有原根：《数论算法》第五章原根与离散对数12/5815≡5（mod17），35≡6（mod17），55≡14，（mod17）75≡10（mod17），95≡12（mod17），115≡11，（mod17）135≡13（mod17），155≡6（m