import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Reader;
import java.io.Writer;
import java.math.BigInteger;
import java.util.Random;
class RSA
{
int P,Q,R,E,D,N,midLen=0,mid2Len=0;
String origin;
String encry;
int mid[]=new int[10000];
int mid2[]=new int[10000];
String decry;
void set2(int p,int q,int e)
{
P=p;
Q=q;
E=e;
R=(P-1)*(Q-1);
N=P*Q;
getD();
}
void reset()
{
P=Q=E=D=R=N=0;
midLen=0;
mid2Len=0;
}
int encrying(int m)
{
int Ms;
Ms=powmod(m, E, N);
return Ms;
}
int decrying(int c)
{
int Md;
Md=powmod(c, D, N);
return Md;
}
void set(int bit1,int bit2)
{
BigInteger t=new BigInteger("2");
Random rn=new Random();
int m;
BigInteger k=t.probablePrime(bit1,new Random());
P=k.intValue();
k=t.probablePrime(bit2,new Random());
Q=k.intValue();
R=(P-1)*(Q-1);
N=P*Q;
while(true)
{
m=rn.nextInt();
if(m>1&&m<R&&gcd(m,R)==1) break;
}
E=m;
getD();
}
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
void getD()
{
int p,r1,r2,r,t1,t2,t;
r1=R; r2=E; t1=0;t2=1;
while(r1!=1)
{
p=r1/r2;r=r1%r2;
t=t1-t2*p;
r1=r2;r2=r;
t1=t2;t2=t;
}
if(t1>=0) D=t1;
else D=t1+R;
}
int powmod(int di,int zi,int mo)
{
int y=1,a=di,k;
while(zi!=0)
{
k=zi%2;zi/=2;
if(k==1) y=(y*a)%mo;
a=(a*a)%mo;
}
return y;
}
}
