欧几里得算法求乘法逆元.doc

《欧几里得算法求乘法逆元.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、扩展的欧几里德算法求乘法逆元#include/*扩展的欧几里德算法求乘法逆元ByVC++6.0陈*/intExtendedEuclid(intf,intd,int*result);intmain(){intx,y,z;z=0;printf("输入两个数：");scanf("%d%d",&x,&y);if(ExtendedEuclid(x,y,&z))printf("%d和%d互素，乘法的逆元是：%d",x,y,z);elseprintf("%d和%d不互素，最大公约数为

2、：%d",x,y,z);return0;}intExtendedEuclid(intf,intd,int*result){intx1,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为两个数的最大公约数，此时返回值为零*/return0;}if(y3==1){*result=y2;/*两个数互素则resutl为其

3、乘法逆元，此时返回值为1*/return1;}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;}}