欢迎来到Python教程自学网!
当前位置: 首页 > Python基础教程 > Python如何用欧几里得求逆元

Python如何用欧几里得求逆元

   

Python如何用欧几里得求逆元

Python用欧几里得求逆元的方法:

建立一个带参数返回值的函数,编写求逆元的一次算法,采用递归的方式循环调用函数,递归直至余数等于零。调用该函数,将需要求的数值带入进去,执行该函数就可以了

示例代码如下:

def ext_gcd(a, b): #扩展欧几里得算法    
    if b == 0:          
        return 1, 0, a     
    else:         
        x, y, gcd = ext_gcd(b, a % b) #递归直至余数等于0(需多递归一层用来判断)        
        x, y = y, (x - (a // b) * y) #辗转相除法反向推导每层a、b的因子使得gcd(a,b)=ax+by成立         
        return x, y, gcd

执行结果如下:

ext_gcd(1848,701)
>>> (-11, 29, 1)