#include <stdio.h>
#include <math.h>
#include <conio.h>
#define I 4
#include<time.h>
long Q[40];
int n,N,M;
typedef long vector[I+1];
long MP(long x,long y,long z);
long inverse(long x,long m),ME(long x,long y,long z);
void BR(long s);
void main()
{/*main*/
//clrscr();
long q1,p1,M1,phi1,e1,d1,xx,xx1,xx2,xx3,
p2,q2,M2,phi2,e2,d2,yy1,yy2,yy3,now0,now,user_time;
now0=time(NULL);
   p1=2699;q1=795659;
   M1=p1*q1;
   printf("p1=%ld q1=%ld M1=%ld  ",p1,q1,M1);
   phi1=(p1-1)*(q1-1);e1=3674911;
   d1=inverse(e1,phi1);
   printf("phi1=%ld e1=%ld d1=%ld \n",phi1,e1,d1);printf("");
   p2=5843;q2=367531;M2=p2*q2;phi2=(p2-1)*(q2-1);
   e2=3674911;printf("p2=%ld q2=%ld M2=%ld  ",p2,q2,M2);
   d2=inverse(e2,phi2);
   printf("phi2=%ld e2=%ld d2=%ld  \n",phi2,e2,d2);printf("");
   xx=12345;
   xx1=ME(xx,M1,e1);xx2=ME(xx1,M1,e1);xx3=ME(xx2,M1,e1);
   yy1=ME(xx3,M2,e2);yy2=ME(yy1,M2,e2);yy3=ME(yy2,M2,e2);
   cprintf("\n KET QUA MA :  ",yy3);
   printf("xx=%ld \n\nxx1=%ld xx2=%ld xx3=%ld \n",xx,xx1,xx2,xx3);
   printf("yy1=%ld yy2=%ld yy3=%ld \n",yy1,yy2,yy3);
   yy2=ME(yy3,M2,d2);yy1=ME(yy2,M2,d2);xx3=ME(yy1,M2,d2);
   xx2=ME(xx3,M1,d1);xx1=ME(xx2,M1,d1);xx=ME(xx1,M1,d1);/* m=c^d modNN=RO */
   cprintf("\n KET QUA DICH : ",xx);
   printf("xx=%ld \n\nxx1=%ld xx2=%ld xx3=%ld  \n",xx,xx1,xx2,xx3);
   printf("yy1=%ld yy2=%ld yy3=%ld \n",yy1,yy2,yy3);
   now=time(NULL);user_time=now-now0;
   printf("\nuser_time = %d seconds ",user_time,"seconds");getchar();
}/*main*/
long x0,m0,p0;
long ME(long x0,long m0,long p0)
{
long A0,p1,Z[40];int i1;
BR(p0);N=n;for (i1=0;i1<=N;i1++) Z[i1]=Q[i1];
/*for (i1=0;i1<=N;i1++)
printf("Q[%d]=%ld \n",i1,Q[i1]);getchar();*/
A0=x0%m0;p1=1;/* A0=x1modMM B pesentation of x1*/
    if(p0>0)
         {
         if (Z[0]>0) p1=A0;
        for(i1=1;i1<=N;i1++)
            {
         A0=MP(A0,A0,m0);
         if(Z[i1]>0) p1=MP(A0,p1,m0);

            }/*i1*/
       }
       return (p1);
    }/*phep tinh luy thua modulo*/
      long s;
    void BR(long s)
   {
      int ii;
      long x,q;
         ii=0;x=s;q=(x>>1);Q[ii]=x-(q<<1);
         while (q>0)
         {
          ii++;x=q;q=(x>>1);Q[ii]=x-(q<<1);
         }
         n=ii;
   }/*Bit-Representation,bieu dien x theo bimary*/

   long x,y,k;
   long MP(long x,long y,long k)
   {
   int ii;long P,t1,t2,Y[40];double tem;t1=x;t2=y;
   if(x<0) {x=-x;x=k-(x%k);} else x=x%k;
   if(y<0) {y=-y;y=k-(y%k);} else y=y%k;
   if ((x==0)||(y==0)) {P=0;goto label1;}
       BR(y); M=n;
   for(ii=0;ii<=M;ii++) Y[ii]=Q[ii];
       if(Y[0]>0) P=x; else P=0;
   for(ii=1;ii<=M;ii++)
         {
         tem=2.0*x;
         if(tem>=k) tem-=k;
         x=(long)tem;
         if(Y[ii]>0)
         {
         tem+=P;
         if(tem>=k) P=(long)(tem-k);
         else P=(long)tem;
      }
       }/*ii*/
      x=t1;
      y=t2;
   label1:return(P);
   }/*phep nhan modulo*/
   long b,a;/*0<b<a,Multicative inverce of  b mod a*/
   long inverse(long b,long a)
   {
    long A,B,d,q,r,x,x1,x2,y,y1,y2,tem;
    A=a;B=b;    /*Dung Beazout*/
     if(b==0)
      {
      d=a;x=1;y=0;
      }/*if*/
      else
      {
      x2=1;x1=0;y2=0;y1=1;
      while (b>0)
        {
       q=a/b;
       r=a-q*b;
       x=x2-q*x1;
       y=y2-q*y1;
       a=b;b=r;x2=x1;x1=x;y2=y1;y1=y;
        }/*while*/
      d=a;x=x2;y=y2;
         }/*else*/
       tem=A*x+B*y-d;
        if(y<0)
        y=A+y;
        return(y);
   }/*inverse*/