欧几里得逆运算java_miracl库的使用之——大数模逆运算

miracl中有许多可以求乘法逆元的函数，在这里主要介绍函数xgcd()

1.函数介绍

2.涵盖内容

3.注意事项

一、xgcd：

函数原型：

int xgcd(x,y,xd,yd,z)

big x,y,xd,yd,z;

在大数库中，xgcd的计算公式是：

On exit z=gcd(x,y)=x.xd+y.yd

我一直百思不得其解，为什么这个函数可以用来计算模逆，直到发现了：拓展的欧几里得算法：

欧几里得算法是什么？

扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a, b)

=d(解一定存在，根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。拓展的欧几里得算法其实又叫做辗转相除法，其实辗转相除法主要用来计算最大公因子，那么为什么可以计算乘法逆元呢？

回答如下： 如果gcd(a，b)=d，则存在m，n，使得d = ma + nb，称呼这种关系为a、b组合整数d，m，n称为组合系数。

当d=1时，有 ma + nb = 1 ，此时就可以看出m是a模b的乘法逆元，n是b模a的乘法逆元。

*

二、核心思想

摘记：

1)我们首先从欧几里得算法学起，欧几里得告诉我们gcd(a,b)=gcd(b,a mod b)；

2)对于不完全为 0 的非负整数 a，b，gcd(a，b)表示 a，b 的最大公约数，必然

存在整数对 x，y ，使得 gcd(a，b)=ax+by。

3)因此，当gcd(a，b)=1时，那么存在ax+by=1，此时有x就是a关于模b的乘法逆元，y也是b关于模a的乘法逆元。

在这里顺便证明一下：

证明拓展的欧几里得算法： 首先，对于整数a和整数b： 由拓展的欧几里得(Euclidean)算法：gcd(a,b)=ax+by

1：当a*b=0时： 当a=0: gcd(a,b)=b; 同理当b=0时： gcd(a,b)=a; x=1，y存在，而可以取任何值，它们是存在的。

2:当a*b!=0的时候： 假设gcd(a,b)=ax[0]+by[0]; 根据辗转相除法， gcd(a,b)=gcd(a,b mod

a); 则说明： gcd(a,b)

=ax[0]+by[0]

=ax[1]+(b-k[1]*a)y[1] ——————k[1]是指b/a取整数部分。

=a(x[1]-k[1]y[1])x[1]+by[1] 所以： x[0]=x[1]-k[1]y[1] y[0]=y[1] 这说明x[0],y[0]的值是否存在，与x[1],y[1]是否存在相关。

当不停地使用2时，一定会出现a或者b为0，则就可以求出x以及y的值。

**函数xgcd(x,y,xd,yd,z)中，就是使用拓展的欧几里得算法，从而计算出：

z=gcd(x,y)=xxd+yyd**

三、注意事项

在使用xgcd求解乘法逆元的时候，必须要小心，因为相互不互素的数是没有乘法逆元的，所以使用前必须对此验证，当然也可以直接验证z，因为z=gcd(a,b);

使用xgcd(a,b,xd,yd,z)计算乘法逆元

当z=1时，xd就是a关于模b的乘法逆元

但是，yd不是关于模a的乘法逆元；

只有当xgcd(b,a,yd,xd,z)且z=1时，

yd才是b关于模a的乘法逆元