Question

c语言，求一个数的逆的模n运算等于多少！

等于多少。。。 其中n=p*q。。 需要分解n 才能算出来比如 等于多少，c语言能得出正确的结果。。

Answer 1

程序如下：

#include <conio.h>
#include <stdio.h>

int ExtEnclid(int d,int f)
{
int x1,x2,x3,y1,y2,y3,t1,t2,t3,k;
if(d>f) d=d+f-(d=f); //交换d和f使得d<f
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(res<0)
{
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