附:求本原元 求一个大素数p很容易,用现成的素性验证算法就 可以了。不过已知一个素数p,求其本原根则很困 难,因为需要将p-1的素因子q1,q2,……qk-1, qk都找出来,然后分别验证gq1modp,gq2 mod p, gqk-1modp, gk mod p,如果都 不等于1,则g是p的一个本原根。而然,如果 p是一个很大的素数,例如128个2进制位的素 数,要分解出p-1的所有素因子来则是一件很困 难的事情。 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 17/81mfy@ustc.edu.cn 现代密码学理论与实践 17/81  求一个大素数 p 很容易，用现成的素性验证算法就 可以了。不过已知一个素数 p，求其本原根则很困 难，因为需要将 p - 1 的素因子 q1，q2，……qk-1， qk都找出来，然后分别验证 gq 1 mod p， gq 2 mod p， ……gq k-1 mod p， gq k mod p，如果都 不等于 1，则 g 是 p 的一个本原根。而然，如果 p 是一个很大的素数，例如 128 个 2 进制位的素 数，要分解出 p - 1 的所有素因子来则是一件很困 难的事情