////////////////////////rsa.cpp//////////////////////////////////

#include<iostream.h>
long int d;
long int n=3337,gn=3220,e=79;
int h(0),t(0);
struct queueinput
{
 char data;
    struct queueinput *next;
};
struct queueinput *top,*base;
struct queueoutput
{
 int num;
 struct queueoutput *next;
};
struct queueoutput *front,*rear,*del;
void main()
{
 long int c,p;
 int pt,ct;
 rear=front=new struct queueoutput;
 void Euclid(long int,long int);
 long int Encryption(int);
    void input();
 Euclid(gn,e);
 cout<<"输入明文：";
 input();
    cout<<"密文: ";
 top=top->next;
 pt=0;
 for(int i=1;i<=h;i++)
 {
  int j(1);
  if(top->data!='0')
  {
   for( j;j<=3 && top->data !='#';j++) //每3个字符一组，将字符转换成数字
   {
      pt=pt*10+(top->data-48);
      top=top->next;
   }
  }
  c=Encryption(pt); //调用函数将数字加密
  if(c==0) //当每组字符中第一个字符等于0时要特别处理
  {
   top=top->next;
   j++;
  }
     cout<<c;
  t++;
        del=new struct queueoutput; //将生成的每个密文存放在队列中，以便逐个解密
  del->num=c;
  rear->next=del;
  rear=del;
        pt=0;
  if(top->data=='#') break;
 }
 long int Decryption(long int);
 cout<<endl<<"明文: ";
 front=front->next;
 for(int z=1;z<=t;z++)
 {
  ct=front->num;
     p=Decryption(ct); //调用解密函数解密
     cout<<p;
  front=front->next;
 }
 cout<<endl;
}

void input()//输入明文
{
 struct queueinput *q;
 base=top=new struct queueinput;
 do
 {   q=new struct queueinput;
  cin>>q->data;
  base->next=q;
  base=q;h++;
 }
 while(q->data != '#');
}

void Euclid(long int m,long int b)  //求乘法逆元
{
 long int a1=1,a2=0,a3=m,b1=0,b2=1,b3=b;
 long int t1,t2,t3;
 int t=1;
 while(t)
 {
  if (b3==0)
  {
   cout<<"不可逆"<<endl;
      return;
  }
     if(b3==1)
  {
      d=b2;
      cout<<"逆元d= "<<b2<<endl;
      return;
  }
     long int q=a3/b3;
     t1=a1-q*b1;
     t2=a2-q*b2;
     t3=a3-q*b3;
     a1=b1;
     a2=b2;
     a3=b3;
     b1=t1;
     b2=t2;
     b3=t3;
 }
}

long int Encryption(int p) //加密函数
{
 long int k=p;
 for(int m=1;m<e;m++)
 {
  k=(k%n)*p;
  
 }
 k=k%n;
 p=k;
 return p;
}

long int Decryption(long int c) //解密函数
{
 long int k=c;
 for(int m=1;m<d;m++)
 {
  k=(k%n)*c;
 }
 c=k%n;
 return c;
}