查找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的乘法逆，扩展欧几里德算法

回答

相关问题