一般根据定义 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的逆元，这样求一个逆元就只是两次查表操作了。
#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, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a, b) =d（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。
下面是一个使用C语言的实现：
intexGcd(int a,int b,int x,int y)
{
if(b==0) //当b==0时，得到解
{
x=1;y=0;
return a;
}
intr=exGcd(b,a%b,x,y);//递归调用自身，求解
intt=x;x=y;y=t-a/b*y;
return r;
}
程序如下：
#include conio.h
#include stdio.h
int ExtEnclid(int d,int f)
{
int x1,x2,x3,y1,y2,y3,t1,t2,t3,k;
if(df) d=d+f-(d=f); //交换d和f使得df
x1=1,x2=0,x3=f;
y1=0,y2=1,y3=d;
while(1)
{
if(y3==0)
{
return 0; //没有逆元,gcd(d,f)=x3
}
if(y3==1)
{
return y2; //逆元为y2,gcd(d,f)=1
}
k=x3/y3;
t1=x1-k*y1, t2=x2-k*y2, t3=x3-k*y3;
x1=y1,x2=y2,x3=y3;
y1=t1,y2=t2,y3=t3;
}
}
int main()
{
int a, n, res;
printf("求 a^(-1) mod n 的值：\n");
printf("a = ");
scanf("%d", a);
printf("n = ");
scanf("%d", n);
res = ExtEnclid(a,n);
if (res == 0)
{
printf("Not Exist!\n");
getch();
return (0);
}
else if(res0)
{
res = res + n;
}
printf("a^(-1) mod n = %d\n", res);
getch();
return (0);
}
计算1/x mod n =x^(-1) mod n
就是求y，满足：
yx = 1 mod n
y是有限域F(n)上x的乘法逆元素
可用扩展的欧几里得算法求乘法逆元
扩展的欧几里德算法简单描述如下：
ExtendedEuclid(d,f)
1 （X1,X2,X3):=(1,0,f)
2 (Y1,Y2,Y3):=(0,1,d)
3 if (Y3=0) then return d'=null//无逆元
4 if (Y3=1) then return d'=Y2 //Y2为逆元
5 Q:=X3 div Y3
6 (T1,T2,T3):=(X1-Q*Y1,X2-Q*Y2,X3-Q*Y3)
7 （X1,X2,X3):=(Y1,Y2,Y3)
8 (Y1,Y2,Y3):=(T1,T2,T3)
9 goto 3
用欧几里得扩展算法
在这里说很难给你讲明白，因为伪代码我记得不是很清晰了，你自己查下书吧，既然有讲AES算法，那书上不可能不提到欧几里得扩展算法的
不行百度一下也可以，我看了一下百度百科的：
欧几里德算法的扩展
扩展欧几里德算法不但能计算(a，b)的最大公约数，而且能计算a模b及b模a的乘法逆元，用C语言描述如下
但是是代码实现的，没有伪代码，还是自己找一下吧
这样可以么？
严格来讲，你的代码是错误的，用int的b接收double型的a的计算结果，是不可以的，即使结果是整数。
结果当然也会出现误差。正确的应该是：
double a=10.3845;
double b;
b=10000*a;
printf("%lf",b);
补充：把上面 printf("%lf",b);改为printf("%.0lf",b); 就能使后面无小数。
重庆分公司
重庆分公司
