用c语言编写扩展欧几里德算法用来求乘法逆元ab=1 mod(n) 要求我输入b,n,求出a。请编译运行通过,谢谢啦

用c语言编写扩展欧几里德算法用来求乘法逆元ab=1 mod(n) 要求我输入b,n,求出a。请编译运行通过,谢谢啦,第1张

#include <stdio.h>

int ExtendedEuclid( int f,int d ,int *result)

int main()

{

int n,b,z

z = 0

printf("输入两个数:\n")

scanf("%d%d",&b,&n)

if(ExtendedEuclid(n,b,&z))

printf("%d和%d互素,乘法的逆元是:谨厅%d\n",b,n,z)

else

printf("%d和%d不互素,最大公约祥档隐数为:%d\n",b,n,z)

return 0

}

int ExtendedEuclid( int f,int d ,int *result)

{

int x1,x2,x3,y1,y2,y3,t1,t2,t3,q

x1 = y2 = 1

x2 = y1 = 0

x3 = ( f>=d )?f:d

y3 = ( f>=d )?d:f

while( 1 )

{

if ( y3 == 0 )

{

*result = x3/* 两个数不互素则result为两个数的最大公约数,此时返回值为零 */

return 0

}

if ( y3 == 1 )

{

*result = y2/* 两个数互素则resutl为其乘法逆元,此时返回值为1 */

return 1

}

q = x3/y3

t1 = x1 - q*y1

t2 = x2 - q*y2

t3 = x3 - q*y3

x1 = y1

x2 = y2

x3 = y3

y1 = t1

y2 = t2

y3 = t3

}

}

/蠢厅*输入两个数:

5 14

5和14互素,乘法的逆元是:3

*/

采春宽用扩展欧几里德算法

首先,欧几里德算法又称辗转相除法,用于求最大公约数,算法如下:

int Gcd(int a, int b)

{

if(b == 0)

return a

return Gcd(b, a % b)

}

扩展欧几里德算法能计算a模键改b及b模a的乘法逆元扒亮亮,如下:

int gcd(int a, int b , int&; ar,int &; br)

{

int x1,x2,x3;

int y1,y2,y3;

int t1,t2,t3;

if(0 == a)

{//有一个数为0,就不存在乘法逆元

ar = 0;

br = 0 ;

return b;

}

if(0 == b)

{

ar = 0;

br = 0 ;

return a;

}

x1 = 1;

x2 = 0;

x3 = a;

y1 = 0;

y2 = 1;

y3 = b;

int k;

for( t3 = x3 % y3 ; t3 != 0 ; t3 = x3 % y3)

{

k = x3 / y3;

t2 = x2 - k * y2;

t1 = x1 - k * y1;

x1 = y1;

x1 = y2;

x3 = y3;

y1 = t1;

y2 = t2;

y3 = t3;

}

if( y3 == 1)

{

//有乘法逆元

ar = y2;

br = x1;

return 1;

}else{

//公约数不为1,无乘法逆元

ar = 0;

br = 0;

return y3;

}

}


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/yw/12475362.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023-05-25
下一篇 2023-05-25

发表评论

登录后才能评论

评论列表(0条)

保存