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

#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

*/

一般根据定义 A^-1＝＝A^254，所以求A的254次方就和困闹可以了，254次又等于尺穗

128+64+32+16+8+4+2＝2*（ 2*（2*（2*（2*（2*（2+1）+1）+1）+1）+1）+1），所以只需要做7次平方和7次乘A。

当然在AES运算中，需要求出全部256个数的倒数，都用这种算法还是比较费的，可以用以下的方法

首先求3的全部255次幂，并做成两个查找表，即正向通过幂次查结果，和反向通过结果查幂次，这个过程可以，因为乘3是最简单的一个乘法 *** 作 ，并且3的255次幂可以遍历整个GF(2,8)空间。

因为3^255=1,所以 当m+n=255时，3^m 和3^n互为倒数，即3^m的逆元就是3^n, n=255-m，那么求一个数A的逆元，可以先通过上面生成的反查表查出A对于3的幂次m，再用255－m=n，在正向表中查出3的n次幂，那个数就是A的逆元，这唤罩样求一个逆元就只是两次查表 *** 作了。

C表示组合数。

C(n,m) 表示n选m的组合数，其中n是下标 , m是上标 (C上面m,下面n)。

nCk是一个整体，是n个元素中，取k个元素的取法的掘让个数，也叫n个元素中，取k

个k组合数，（C代表组合），算法是：

nCk＝n!/k!（n-k）!＝n（n-1）……（n-k+1）/k!

等于从n开始连续递减的m个自然数的积除以从1开始连续递增的m个自然数的积。

该概率公式的推导过程：

在这个证明中，表示n次实验中，成功的k次，取法的个数。

每次取定后，k次成功，n-k次失败，概率用乘法P＝p^k*(1-p)^(n-k)

总共有铅梁nCk个取法，即nCk个情况，概率用加法，每个情况的概率又相同，所以

成为nCk倍。

扩展资料：

求组合数C的方法：

1、当n,m都很小的时候可以利用杨辉三角直接求。

C(n,m)=C(n-1,m)+C(n-1,m-1)；

2、利用乘法逆元

乘法逆元：(a/b)%mod=a*(b^(mod-2)) mod为素判激局数。

逆元可以利用扩展欧几里德或欧拉函数求得。

3、当n和m比较大，mod是素数且比较小的时候（10^5左右），通过Lucas定理计算

参考资料来源：百度百科-组合数

---