/*
*This program is about the ElGamal algorithm.
*Author : Ting
*E-mail:kilvdn@yahoo.com.cn 
*Addr: China Unversity of Geoscience ( WuHan )
*Note: ElGamal algorithm is based on the Discrete Logarithm Problem
*/

＃i nclude <stdio.h>
int c1 , c2 , p , a , d , m , k , x , y ;

int Mod(int x,int y,int m){//模平方的运算
    int a,b;
    a=1;
    b=x;
    while( y ){
       if( y % 2 == 1 )
       a = a * b % m ;
       y /= 2 ;
       b = b * b % m ;
    }
    return a;
}

/**********************************************
*      求逆元　　用的是ext_euclid算法         *
***********************************************/
int Inverse(int a,int b,int &x,int &y)   
{
   int t,d;
   if (b==0) { x=1; y=0; return a; }
   d=Inverse(b,a%b,x,y);
   t=x;
   x=y;
   y=t-a/b*y;
   return d;
}

void  Encry(int p,int a,int d,int m,int k)
{
    int y , u ;
    y = Mod( a , d , p ) ;
    u = Mod( y , k , p ) ;
    c1 = Mod( a , k , p ) ;
    c2 = u * m % p ;
    printf("c1=%d c2=%d ",c1,c2) ;
}

void  Decry(int c1,int c2,int d,int p)
{
    int v , v_1 , m ;
    v = Mod ( c1 , d , p ) ;
    Inverse( v , p , x , y ) ;
    x = ( x + p ) % p ;
    m = c2 * x % p ;
    printf("m=%d ", m ) ;
}

int main()
{
     int flag ;    
     while( 1 ){
  printf("请选择要执行的操作： 1.Encryption  2.Decryption ");        
     scanf("%d",&flag);
      if(1==flag){
         printf("please input (p,a,d,m,k): ");
         scanf("%d%d%d%d%d",&p,&a,&d,&m,&k);
         Encry( p , a , d , m , k ) ;
        }
     else{
         printf("please input (c1,c2,d,p): ");
         scanf("%d%d%d%d",&c1,&c2,&d,&p);
         Decry( c1 , c2 , d , p ) ;
        }
 }
 return 0;
}
/*
 p = 2579
 a = 2
 d = 765
 m = 1299
 k = 853
*/