求 Z(n) 中 x 的乘法逆元,扩展欧几里德算法
Finding multiplicative inverse of x in Z(n), extended Euclides algorithm
我正在尝试使用 GMP 库查找 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);
}
它适用于所有小数字和一些大数字,但不适用于所有数字,我不知道为什么。它不起作用的示例数字:
a=99493485436357509294299436068793093643611893389896126764674829386592836165461754466092785338067969036756243799506670417432259164622123562781847156006846186608672621538507317131150760491084706497192710261706218845591564505899259562270249156644155861984060987885202877640033289062925176647874893491223532714128
b=202287573793610924311033969010234326099
如果我将 b 更改为:
b=202287573793610924311033969010234326199
它工作正常(我把右边的第一个0改成了1);我得到的结果是:
-26280231501456618600907242915048902345641123248519760433640466576442417888637174268721528225514196371138187569270563190841794774411834326405888357503240710494456394764379952360665884114850067939183395690214208147924280567331029828334399167395301049535292042342359035346464834873473183771024039179653285711685
由 GMP 函数计算并由我在等式 b*b^-1 ≡ 1 mod (a)
中检查的正确结果是:
73213253934900890693392193153744191297970770141376366331034362810150418276824580197371257112553772665618056230236107226590464390210289236375958798503605476114216226774127364770484876376234638558009314571492010697667283938568229733935849989248854812448768945542843842293568454189451992876850854311570247002443
如果 a 和 b 互质,扩展欧几里德算法找到 x 和 y 使得
x a + y b == 1
但 x 或 y 可能为负数。对于 y = b 模 a 的倒数,
if y < 0 then y = y + a,
这会将 y 转换为模 a 的正确值(请注意我之前的评论)。
Wiki 示例发现 t = 模 n 的倒数,并具有相同的检查:
if t < 0 then t = t + n
http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Modular_integers
我正在尝试使用 GMP 库查找 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);
}
它适用于所有小数字和一些大数字,但不适用于所有数字,我不知道为什么。它不起作用的示例数字:
a=99493485436357509294299436068793093643611893389896126764674829386592836165461754466092785338067969036756243799506670417432259164622123562781847156006846186608672621538507317131150760491084706497192710261706218845591564505899259562270249156644155861984060987885202877640033289062925176647874893491223532714128
b=202287573793610924311033969010234326099
如果我将 b 更改为:
b=202287573793610924311033969010234326199
它工作正常(我把右边的第一个0改成了1);我得到的结果是:
-26280231501456618600907242915048902345641123248519760433640466576442417888637174268721528225514196371138187569270563190841794774411834326405888357503240710494456394764379952360665884114850067939183395690214208147924280567331029828334399167395301049535292042342359035346464834873473183771024039179653285711685
由 GMP 函数计算并由我在等式 b*b^-1 ≡ 1 mod (a)
中检查的正确结果是:
73213253934900890693392193153744191297970770141376366331034362810150418276824580197371257112553772665618056230236107226590464390210289236375958798503605476114216226774127364770484876376234638558009314571492010697667283938568229733935849989248854812448768945542843842293568454189451992876850854311570247002443
如果 a 和 b 互质,扩展欧几里德算法找到 x 和 y 使得
x a + y b == 1
但 x 或 y 可能为负数。对于 y = b 模 a 的倒数,
if y < 0 then y = y + a,
这会将 y 转换为模 a 的正确值(请注意我之前的评论)。
Wiki 示例发现 t = 模 n 的倒数,并具有相同的检查:
if t < 0 then t = t + n
http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Modular_integers