指数函数之特性(续) 本原元素举例:p=11,g=2,中(p-1)=中(10)=4,即1,3,7,9与 p-1互素。若g=2为模p之本原元素,则 21=2,23=8,27=7,29mod11=6均为模11之本原元素。找到 个本原元素后可以容易找到所有本原元素,问题是如何找到第 个本原元素。 算法如下: P1.利用素性验证算法,生成一个大素数q; P2.令p=q*2+1; P3.利用素性验证算法,验证p是否是素数,如果否,则跳 转到P1; P4.生成一个随机数g,1<g<p-1; P5.验证g2modp和 gq mod p都不等于1,否则跳转到 P4 cP6.g是大素数p的本原根。 ash mfy@ustc.edu.cn 现代密码学理论与实践 18/81mfy@ustc.edu.cn 现代密码学理论与实践 18/81 本原元素举例：p=11, g=2, φ(p-1)= φ(10)=4, 即1, 3, 7, 9与 p-1互素。若 g=2为模p之本原元素, 则 21=2, 23=8, 27=7, 29 mod 11=6均为模11之本原元素。找到 一个本原元素后可以容易找到所有本原元素, 问题是如何找到第一 个本原元素。  算法如下： ◦ P1. 利用素性验证算法，生成一个大素数q； P2. 令 p = q * 2 + 1； P3. 利用素性验证算法，验证 p 是否是素数，如果否，则跳 转到P1； P4. 生成一个随机数 g，1 < g < p - 1； P5. 验证 g2 mod p 和 gq mod p 都不等于 1，否则跳转到 P4； P6. g 是大素数 p 的本原根