#include<iostream>
#include<cmath>
#include<string>

using namespace std;
int miwen[1024];



//////判斷輸入的數是否為素數//////
bool pdprime(long m)
{
	bool pd;
	int i;
	for(i = 3;i < m;i= i + 2)
		if(m % i ==0)
			break;
	 if(m == i)
		pd = 1;
	else 
		pd = 0;
	return pd;
}

///// 判斷兩個數是否互素/////
bool pdhusu(long a,long b)
{
	int t0 = 0, t = 1,s0 = 1,s = 0 , q , r ;
	int temp;
	bool pdhs;
	q = a / b;
	r = a - q * b;

	while ( r > 0)
	{
		
		temp = t0 - q * t;
		t0 = t;
		t = temp;
		temp = s0 - q * s;
		s0 = s;
		s = temp;
		a = b;
	    b = r;
		q = a / b;
		r = a - q * b;	
		
	}
	r = b;

	if ( r == 1)
		pdhs = 1;
	else 
		pdhs = 0;
	return pdhs;


}

/////求d 的值//////


int qiuni(long a, long b)
{
	int t0 = 0, t = 1,s0 = 1,s = 0 , q , r , u , v , d;
	int temp;

	u = a;
	v = b;
	q = a / b;
	r = a - q * b;

	while ( r > 0)
	{
		
		temp = t0 - q * t;
		t0 = t;
		t = temp;
		temp = s0 - q * s;
		s0 = s;
		s = temp;
		a = b;
	    b = r;
		q = a / b;
		r = a - q * b;	
		
	}
	r = b;


	if ( r == 1)
	{
		cout << endl;
		cout << "s = " << s << endl;		
		cout << "t = " << t << endl;
		cout << "r = " << s << " * " << u << " + " ;
		cout << t << " * " << v << endl << endl;
		
		cout << u << "和"<< v << "互素，滿足條件" << endl << endl;
		if(t > 0)
			d = t % u;
		else
			d = (u + t) % u;
			
		return d;
	}
	else 
	{
		cout << u << " 和 " << v << "不互素，不滿足條件" << endl;
		return false;
	}
	


}
////// 加密/////

void jiami(string data,int p ,int d)

{
	char c;
	int u = 0;
	cout << "加密后的結果為：" << endl ;
	for(int i = 0;i < data.size(); i ++)
	{
		miwen[i] = data.at(i);
		c = miwen[i];
		for(int j = 1;j < d ;j ++)
			miwen[i] = miwen[i] * c % p;
		
		cout << miwen[i] << ' ';

	}

}


////....解密....//////
void hjiemi(int z1,int x)
{
	int c;
	char g;
	int jiemi[1024];
	cout << "解密后的結果為：" << endl ;
	for(int i = 0;i < 1024; i ++)
	{
		jiemi[i] = miwen[i];	
		c = miwen[i];
		for(int j = 1;j < z1 ;j ++)	
			jiemi[i] = jiemi[i] * c % x;
	
		if(jiemi[i] != 0)
		{
			g = jiemi[i];
			cout << g;
		}

	}

}




int main()
{
	long p , q , n , m , a = 0 , d;
	char c;
	string data;
	cout << "請輸入一段明文 ：" << endl; 
	getline(cin, data, '\n');
    cout << "請輸入 p 的值  = ";
	cin >> p ;
     cout << "請輸入 q 的值  = ";
	cin >> q ;
	cout << pdprime(p) << ' ' << pdprime(q) << endl;
	if(pdprime(p) == 1 && pdprime(q) == 1)
	{
		cout << "輸入的 p 和 q 滿足條件" << endl << endl;
		n = p * q;
		m
			= (p - 1) * (q - 1);
cout << "所計算φ(n) = (p - 1) * (q - 1)的值為"<<m<<endl;
		cout << "請輸入一個小于" <<m<< "的隨機整數 e = ";
		cin >> a;
		cout << endl;
		if(pdhusu(a , m) == 1)
		{
			d = qiuni(m, a);
			cout << "a 的逆模 φ(n) 為 " << d << endl << endl;
			jiami(data,n,a);

			cout << endl << endl;
			cout << "公鑰為 :" << n << ' ' << a << endl;
			cout << "私鑰為 :" << p << ' ' << q << ' ' << d << endl << endl;

			cout << "是否解密（y/n）"<< endl;
			cin >> c;
			if(c == 'y')
				hjiemi(d,n);
			else
				exit(1);
		}
		else
			cout << "輸入的小于 n 的隨機整數 a 和 φ(n) 不互素" << endl;


	}

	else
		cout << " 輸入的p 和 q不全為素數 " << endl;


system("pause");
}