求乘法逆元c语言版,C语言实现求乘法逆元

如果ax≡1 (mod p),且gcd(a,p)=1(a与p互质)，则称a关于模p的乘法逆元为x。

1.头文件

#include

#include

#include

2.求需要存储的空间

int mod_inv_a(int a, int b, int *len)

{

int d = 0;

int i = 0;

while(a)

{

d = b % a;

b = a;

a = d;

i++;

}

*len = i;

return 0;

}

3.求乘法逆元

int mod_inv_b(int a, int b, int len)

{

int c[len];

int d = 0;

int e = 0;

int f = 0;

int g = b;

int n = 0;

int i = 0;

memset(c, 0x00, sizeof(c));

while(a)

{

d = b % a;

c[i] = b / a;

b = a;

a = d;

//printf("a=[%d], b=[%d], c=[%d]\n", a, b, c[i]);

i++;

}

//printf("len=[%d]\n", len);

d = 1;

e = c[i-2];

//printf("i-2=[%d]\n", i-2);

n = i-1;

i = 1;

while(i < n)

{

//printf("i=[%d], n-1-i=[%d]\n", i, n-1-i);

f = c[n-1-i] * e + d;

f %= g;

d = e;

e = f;

i++;

}

//e %= g;

if(len % 2 == 0) e = g - e;

return e;

}

4.接口封装

int mod_inv(int a, int b)

{

int len = 0;

mod_inv_a(a, b, &len);

return mod_inv_b(a, b, len);

}

5.主函数部分

int main()

{

int a = 19;

int b = 97;

int d = 0;

d = mod_inv(a, b);

printf("d=[%d]\n", d);

printf("e=[%d]\n", d * a % b);

return 0;

}