重庆分公司,新征程启航
为企业提供网站建设、域名注册、服务器等服务
(1)用循环一个个试
成都创新互联公司服务项目包括滦州网站建设、滦州网站制作、滦州网页制作以及滦州网络营销策划等。多年来,我们专注于互联网行业,利用自身积累的技术优势、行业经验、深度合作伙伴关系等,向广大中小型企业、政府机构等提供互联网行业的解决方案,滦州网站推广取得了明显的社会效益与经济效益。目前,我们服务的客户以成都为中心已经辐射到滦州省份的部分城市,未来相信会继续扩大服务区域并继续获得客户的支持与信任!
(2)要快一点,试试用扩展欧几里得算法(就是利用辗转相除找最大公因数,算法过程中记录一些东西,就知道是否有逆,有逆直接可求出来),
密码学书上均有,你也可在网上找
估计没有什么人会解释你的问题的。做加密运算本身就是需要很复杂的计算的。
我曾阅读过md5加密算法的程序,那可是3X3X3的矩阵运算。是真要用到大学的线性代数的,而且其运算还比较复杂。加密的狠麻烦的。
汗,这是欧几里得算法求最大公约数..
int r=m%n;
while(r!=0)
{ m=n;
n=r;
r=m%n;
}
这是欧几里得算法的实现...
欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理:
定理:gcd(a,b) = gcd(b,a mod b)
证明:a可以表示成a = kb + r,则r = a mod b
假设d是a,b的一个公约数,则有
d|a, d|b,而r = a - kb,因此d|r
因此d是(b,a mod b)的公约数
假设d 是(b,a mod b)的公约数,则
d | b , d |r ,但是a = kb +r
因此d也是(a,b)的公约数
因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证
1、 欧几里德算法:给定两个正整数m和n,求他们的最大公因子,即能够同时整除m和n的最大的正整数。
E1:【求余数】以n除m并令r为所得余数(我们将有0=rn)。
E2:【余数为0?】若r=0,算法结束;n即为答案。
E3:【互换】置mßn,nßr,并返回步骤E1.
证明:
我们将两个正整数m和n的最大公因子表示为:t = gcd(m,n);
重复应用等式:gcd(m,n)= gcd(n,m mod n)直到m mod n 等于0;
m可以表示成m = kn + r;则 r = m mod n , 假设 d是 m 和 n的一个公约数,则有:
d|m 和 d|m 而 r =m – kn ,因此 d|r ,因此 d 是 (n,m mod n) 的公约数;假设 d 是 (n,m mod n) 的公约数,
则 d|n ,d|r ,但是 m=kn+r ,因此 d 也是 (a,b) 的公约数;因此 (a,b) 和
(b,a mod b) 的公约数是一样的,其最大公约数也必然相等,得证。
具体步骤描述如下:
第一步:如果 n=0 ,返回 m 的值作为结果,同时过程结束;否则,进入第二步。
第二步:用 n 去除 m ,将余数赋给 r 。
第三步:将 n 的值赋给 m,将 r的值赋给 n,返回第一步。
伪代码描述如下:
Euclid(m,n)
// 使用欧几里得算法计算gcd(m,n)
// 输入:两个不全为0的非负整数m,n
// 输出:m,n的最大公约数
while n≠0 do
r ← m mod n
m ← n
n ← r
注:(a,b) 是 a,b的最大公因数
(a,b)|c 是指 a,b的最大公因数 可以被c整除。
java实现:
package algorithm;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class GreatestCommonDivisor {
int a,b,temp = 0;
public static void main(String args[]) throws IOException {
GreatestCommonDivisor gcd = new GreatestCommonDivisor();
gcd.readNum();
gcd.MaxNum();
System.out.print(gcd.a+"和"+gcd.b+"的最大公约数是:");
while (gcd.b != 0) {
gcd.temp = gcd.b;
gcd.b = gcd.a % gcd.b;
gcd.a = gcd.temp;
}
System.out.println(gcd.temp);
}
//输入两个正整数,中间用空格分开.
public void readNum() throws IOException{
BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
String str = buf.readLine();
for(int i = 0;istr.length();i++){
if(str.charAt(i)==' ' temp == 0){
a = Integer.parseInt(str.substring(temp,i));
temp = i;
b = Integer.parseInt(str.substring(temp+1,str.length()));
break;
}
}
}
public void MaxNum(){
if (a b) {
temp = b;
b = a;
a = temp;
}
}
}