JAVA实现扩展欧几里德算法求乘法逆元

标签:
javaeuclid550mod1769乘法逆元扩展欧几里德 |
分类: java |
public int niyuan(int a,int b)//求550关于模1769的乘法逆元
// 550*X(mod1769)=1
// niyuan(1769,550)
{
int[] m={1,0,a};
int[] n={0,1,b};
int[] temp=new int[3];
int q=0; //初始化
boolean flag=true;
while(flag)
{
q=m[2]/n[2];
for(int i=0;i<3;i++)
{
temp[i]=m[i]-q*n[i];
m[i]=n[i];
n[i]=temp[i];
}
if(n[2]==1)
{
if(n[1]<0)
{
n[1]=n[1]+a;
}
return n[1];
}
if(n[2]==0)
{
flag=false;
}
}
return 0;
}
运行结果:
http://s11/mw690/4da051a6ge14ec8b48a8a&690
伪代码:
1.(A1, A2, A3) ←(1,0,m); (B1, B2, B3) ←(0,1,b)
2.If B3 = 0 return A3 = gcd(m, b); no inverse
3.If B3 = 1 return B3 = gcd (m, b); B2 = b-1 mod m
4.Q = L A3/B3 」
5.(T1, T2, T3) ←(A1 – QB1, A2 – QB2, A3 – QB3)
6.(A1, A2, A3) ←(B1, B2, B3)
7.(B1, B2, B3) ←(T1, T2, T3)
8.Goto 2