public class EuclidExtend {
public int gcd(int a ,int b)
{
int temp=0;
//System.out.println("start:");
if(b!=0){
int i=1;
for(i=1;a-b*i>=0;i++)
{ ; }
temp=b;
b=a-b*(i-1);
a=temp;
//System.out.println("next step:"+a+","+b);
return gcd(a,b);
}
else{
System.out.println("最大公约数:" +a);
return a;
}
}
public void compute(int num1,int num2)
{
int Q,A3,B3,T1,T2,T3,A1=1,A2=0,B1=0,B2=1;
A3=num1;
B3=num2;
if(gcd(A3,B3)==1){
System.out.println(num1+"和"+num2+"有逆元!");
do{
if(B3==0){
A3=gcd(A3, B3);
System.out.println("no inverse.");
}
else if(B3==1){
B3=gcd(A3, B3);
if(B2<0)
{
B2=B2+num1;
}
System.out.println("逆元:"+B2);
break;
}
Q=(int)Math.floor(A3/B3);
T1=A1-Q*B1;
T2=A2-Q*B2;
T3=A3-Q*B3;
A1=B1;
A2=B2;
A3=B3;
B1=T1;
B2=T2;
B3=T3;
}while(true);
}
else{
System.out.println(num1+"和"+num2+"无逆元");
}
}
public static void main(String args[]){
int num1=1759,num2=550;
EuclidExtend ee=new EuclidExtend();
ee.compute(num1, num2);
}
}
分享到:
相关推荐
欧几里得算法及扩展的欧几里得算法的C++实现。包括.cpp,.exe可执行文件。我的作业。对于密码学和C++初学者有用处,希望对大家有帮助。
扩展欧几里得算法求逆元
当a,b,且a互质时,计算ax+by=1的值, 是计算RSA密钥的基本步骤之一。
此为扩展欧几里得算法求乘法逆元的完整程序,图形界面,使用 vc6.0 完成,完全标准正式的格式,绝对值10积分,有完整的代码,请使用 vc6.0 打开 DSW 工程文件,然后就可完全执行。
java语言实现的欧几里得算法,求最大公约数,以及满足(a,b)=x*a+y*b的x和y
欧几里得是数论中的一个最初步的概念,它用来判断两个数的最大公因子,扩展的欧几里得能够进一步实现在两个数互素情况下的乘法可逆元。求可逆元是一些算法的基础。
包括完整的c语言实现扩展的欧几里得算法代码截图和相关代码说明以及程序截图
信息安全入门基本必备,将基础的欧几里得扩展所得的扩展欧几里得算法。
本算法实现了用扩展欧几里得的方法求最大公因子和模逆元的方法,可以直接运行。
matlab的M函数文件,附带了函数的使用说明了
用扩展欧几里得算法求任意两个数字的最大公因数
扩展欧几里得求逆-扩展欧几里得算法求乘法逆元
对欧几里得算法的全部思想简要描述,对不同阶段不同人对算法的不同优化,包括knuth大神的亚二次算法
35扩展欧几里得算法1
介绍了扩展欧几里得算法的实现代码,有需要的朋友可以参考一下
MATLAB实现的扩展欧几里得算法
欧几里得/扩展欧几里得算法欧几里得算法:扩展欧几里得:描述:设a,b不全为0,则存在整数x,y,使得:$$gcd(a,b)=xa+yb$$现在假设,我们要求一个
密码学考试复习(关于快速指数算法和扩展欧几里得求逆元),之前考试自己整理的,今天又要学了。里面的算法还能看,还整理的比较透彻当时。备用了留在这。不知道为什么之前上传的xmind一点就跳转到别的页面了,这次...