查找Z（n）中x的乘法逆，擴展歐幾里德算法

我想用GMP庫找到x的乘法逆;我知道有一個內置函數，但我想寫我自己的。
這是我的擴展歐幾里德算法的實現：查找Z（n）中x的乘法逆，擴展歐幾里德算法

void extended_euclides(mpz_t r,mpz_t x,mpz_t y,mpz_t a, mpz_t b){ 
    mpz_t r_2,r_1,x_2,x_1,y_2,y_1,q,tmp; 

    mpz_inits(r,x,y,NULL); 

    mpz_init_set(r_2,a); 
    mpz_init_set(r_1,b); 
    mpz_init_set_ui(x_2,1); 
    mpz_init_set_ui(y_2,0); 
    mpz_init_set_ui(x_1,0); 
    mpz_init_set_ui(y_1,1); 
    mpz_init_set_ui(q,0); 
    mpz_init_set_ui(tmp,0); 

    do{ 
     mpz_fdiv_qr(q,r,r_2,r_1); 
     //x 
     mpz_mul(tmp,q,x_1); 
     mpz_sub(x,x_2,tmp); 
     //y 
     mpz_mul(tmp,q,y_1); 
     mpz_sub(y,y_2,tmp); 

     mpz_set(x_2,x_1); 
     mpz_set(x_1,x);  

     mpz_set(y_2,y_1); 
     mpz_set(y_1,y); 

     mpz_set(r_2,r_1); 
     mpz_set(r_1,r); 
    }while(mpz_cmp_ui(r,0)!=0); 

    mpz_set(r,r_1); 
    mpz_set(x,x_2); 
    mpz_set(y,y_2); 

    mpz_clears(r_2,r_1,x_2,y_2,x_1,y_1,q,tmp,NULL); 
}

它正常工作，所有小號碼和一些大的數字，但不是所有的，我不知道爲什麼。實施例編號爲它不工作：

一個= 99493485436357509294299436068793093643611893389896126764674829386592836165461754466092785338067969036756243799506670417432259164622123562781847156006846186608672621538507317131150760491084706497192710261706218845591564505899259562270249156644155861984060987885202877640033289062925176647874893491223532714128
B = 202287573793610924311033969010234326099

如果我b變更

到：

b = 202287573793610924311033969010234326199

它工作正常（我從右側更改爲0）1;結果我得到的是：

-26280231501456618600907242915048902345641123248519760433640466576442417888637174268721528225514196371138187569270563190841794774411834326405888357503240710494456394764379952360665884114850067939183395690214208147924280567331029828334399167395301049535292042342359035346464834873473183771024039179653285711685

正確的結果，通過GMP函數計算公式b*b^-1 ≡ 1 mod (a)由我檢查，方法是：

來源

2015-11-10 Bartek

你在惡劣的情況下，得到什麼輸出？預期產出是多少？ –

@Bartek - 如果您得到否定結果，請將{a}添加到結果中。根據前5位數字，似乎它工作正常。 – rcgldr

@rcgldr，a =（p-1）（q-1），p，q是素數，b我選擇與a互質。我相信粘貼在我的問題中的b是相反的。 GMP功能返回正確的結果。我不明白爲什麼我的實現有時會返回適當的結果，而另一個則是在GMP函數返回相同數字的適當結果時。 – Bartek

如果a和b是互質數，擴展歐幾里得算法找到x和y，使得

x a + y b == 1

但X或Y可以是負的。對於y = b模a的倒數，

if y < 0 then y = y + a,

它會將y轉換爲適當的模數a（注意我的事先評論）。

維基例如找到一個模n T =逆，並具有相同的檢查：

if t < 0 then t = t + n

http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Modular_integers

來源

2015-11-13 17:18:51 rcgldr

查找Z（n）中x的乘法逆，擴展歐幾里德算法

回答

相關問題