アストルファの幻想郷
やりたくないこともやる
离散对数问题
发表于 2022-08-15 | 更新于: 2022-08-15 | 分类于 Crypto
前置知识 欧拉, 欧拉定理, 模反元素(模逆元) 可参见: RSA加密
阶
由欧拉定理可知,若n,a为正整数,且n,a互素(即gcd(a,n)=1),则 a^phi(n) = 1 (mod n).
因此满足同余式 a^m = 1 (mod n)的最小正整数m存在,这个m称作a模n的阶,记作delta(n,a).
若n,a为正整数,且n,a互质,如果 gcd(a,n)=1 且 delta(n,a) = phi(n), 则称a为模n的原根.
简单来说,使该式成立的d可能有