inverse.h

一个关于密码算法RSA的实现程序

//the function used to compute the inverse of a module n
#include <iostream.h>
#include <math.h>
int ExtendEuclid(int a, int n)
{
  int x1,x2,x3;
  int y1,y2,y3;
  int temp1,temp2,temp3;
  int q;
  x1=1;
  x2=0;
  x3=n;
  y1=0;
  y2=1;
  y3=a;
  if(y3==0)
  {
	  return 0;
  }
  else
  {
	  while(y3!=1)
	  {
		  q=x3/y3;
          temp1=x1-q*y1;
          temp2=x2-q*y2;
          temp3=x3-q*y3;

          x1=y1;
          x2=y2;
          x3=y3;

          y1=temp1;
          y2=temp2;
          y3=temp3;
	  }
	  return y2;
  }
}