euclide.cpp

来自「一个加解密程序」· C++ 代码 · 共 27 行

#include <stdio.h>
//solve: ab=r0 (mod c) return a
int inv(int b, int r0, int c)
{
	int r1,m1;
	r1=c%b;
	if(r1==1)
		return ((b-r0%b)*c+r0)/b;
	else {
		m1=inv(r1, b-r0%b, b);
		return (m1*c+r0)/b;
	}
}
void main()
{ 
	int b,r0,c,a;
	printf("b,r0,c= "); scanf("%d,%d,%d",&b,&r0,&c);
	a=inv(b,r0,c);
	printf("a= %1d\n",a);
	if((a*b)%c==r0)
		printf("OK!\n");
	else
		printf("Error!\n");

}