java代碼如何實現(xiàn)a^-1(mod b)？

（1）用循環(huán)一個個試

成都創(chuàng)新互聯(lián)公司服務項目包括灤州網站建設、灤州網站制作、灤州網頁制作以及灤州網絡營銷策劃等。多年來，我們專注于互聯(lián)網行業(yè)，利用自身積累的技術優(yōu)勢、行業(yè)經驗、深度合作伙伴關系等，向廣大中小型企業(yè)、政府機構等提供互聯(lián)網行業(yè)的解決方案，灤州網站推廣取得了明顯的社會效益與經濟效益。目前，我們服務的客戶以成都為中心已經輻射到灤州省份的部分城市，未來相信會繼續(xù)擴大服務區(qū)域并繼續(xù)獲得客戶的支持與信任！

（2）要快一點，試試用擴展歐幾里得算法（就是利用輾轉相除找最大公因數(shù)，算法過程中記錄一些東西，就知道是否有逆，有逆直接可求出來），

密碼學書上均有，你也可在網上找

java 密碼學 擴展歐幾里得

估計沒有什么人會解釋你的問題的。做加密運算本身就是需要很復雜的計算的。

我曾閱讀過md5加密算法的程序，那可是3X3X3的矩陣運算。是真要用到大學的線性代數(shù)的，而且其運算還比較復雜。加密的狠麻煩的。

java 計算最小公倍數(shù)的問題

汗,這是歐幾里得算法求最大公約數(shù)..

int r=m%n;

while(r!=0)

{ m=n;

n=r;

r=m%n;

}

這是歐幾里得算法的實現(xiàn)...

歐幾里德算法又稱輾轉相除法，用于計算兩個整數(shù)a，b的最大公約數(shù)。其計算原理依賴于下面的定理：

定理：gcd(a,b) = gcd(b,a mod b)

證明：a可以表示成a = kb + r，則r = a mod b

假設d是a,b的一個公約數(shù)，則有

d|a, d|b，而r = a - kb，因此d|r

因此d是(b,a mod b)的公約數(shù)

假設d 是(b,a mod b)的公約數(shù)，則

d | b ， d |r ，但是a = kb +r

因此d也是(a,b)的公約數(shù)

因此(a,b)和(b,a mod b)的公約數(shù)是一樣的，其最大公約數(shù)也必然相等，得證

關于歐幾里得算法，主要是看不懂。請高手指點迷津。。。。

1、 歐幾里德算法：給定兩個正整數(shù)m和n，求他們的最大公因子，即能夠同時整除m和n的最大的正整數(shù)。

E1：【求余數(shù)】以n除m并令r為所得余數(shù)（我們將有0=rn）。

E2：【余數(shù)為0？】若r=0，算法結束；n即為答案。

E3：【互換】置m?n,n?r,并返回步驟E1.

證明：

我們將兩個正整數(shù)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的一個公約數(shù)，則有：

d|m 和 d|m 而 r =m – kn ，因此 d|r ，因此 d 是 (n,m mod n) 的公約數(shù)；假設 d 是 (n,m mod n) 的公約數(shù)，

則 d|n ，d|r ，但是 m=kn+r ，因此 d 也是 (a,b) 的公約數(shù)；因此 (a,b) 和

(b,a mod b) 的公約數(shù)是一樣的，其最大公約數(shù)也必然相等，得證。

具體步驟描述如下：

第一步：如果 n=0 ，返回 m 的值作為結果，同時過程結束；否則，進入第二步。

第二步：用 n 去除 m ，將余數(shù)賦給 r 。

第三步：將 n 的值賦給 m，將 r的值賦給 n，返回第一步。

偽代碼描述如下：

Euclid(m,n)

// 使用歐幾里得算法計算gcd(m,n)

// 輸入：兩個不全為0的非負整數(shù)m，n

// 輸出：m，n的最大公約數(shù)

while n≠0 do

r ← m mod n

m ← n

n ← r

注：(a,b) 是 a,b的最大公因數(shù)

(a,b)|c 是指 a,b的最大公因數(shù) 可以被c整除。

java實現(xiàn)：

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+"的最大公約數(shù)是:");

while (gcd.b != 0) {

gcd.temp = gcd.b;

gcd.b = gcd.a % gcd.b;

gcd.a = gcd.temp;

}

System.out.println(gcd.temp);

}

//輸入兩個正整數(shù),中間用空格分開.

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;

}

}

}