单选题
适中
#22140
考虑一个自然数n以及一个模数m,你需要计算n的逆元(即n在模m意义下的乘法逆元)。下列哪种算法最为合适?( )
考虑一个自然数n以及一个模数m,你需要计算n的逆元(即n在模m意义下的乘法逆元)。下列哪种算法最为合适?( )
答案与解析
正确答案:B
解析
如果一个线性同余方程ax≡1(modb),则x称为a mod b的逆元,记作a-1。扩展欧几里德算法找到两个整数x和y满足ax+by=gcd(a, b)。当a和b互质时,即gcd(a,b)=1,这个方程变为ax+by=1。在模b意义下,ax与1在模b时同余,因此x就是a的模b的逆元。快速幂法使用了费马小定理,要求b是一个素数;而扩展欧几里得法只要求gcd(a,b)=1