加载中…
个人资料
_src
_src
  • 博客等级:
  • 博客积分:0
  • 博客访问:2,065
  • 关注人气:30
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

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

(2013-07-12 19:15:19)
标签:

java

euclid

550mod1769

乘法逆元

扩展欧几里德

分类: 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

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有