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

using namespace std;

// 定义RSA类
class RSA
{
private:
    unsigned long int n; // 公钥
    unsigned long int e; // 公钥
    unsigned long int d; // 私钥
    unsigned long int p; // 素数p
    unsigned long int q; // 素数q

public:
    // 构造函数
    RSA(unsigned long int p, unsigned long int q)
    {
        this->p = p;
        this->q = q;
        n = p * q;
        unsigned long int fn = (p - 1) * (q - 1);
        e = 2;
        while (e < fn)
        {
            if (gcd(e, fn) == 1)
                break;
            else
                e++;
        }
        d = 1;
        while ((d * e) % fn != 1)
            d++;
    }

    // 加密
    unsigned long int encrypt(unsigned long int m)
    {
        return (unsigned long int)pow(m, e) % n;
    }

    // 解密
    unsigned long int decrypt(unsigned long int c)
    {
        return (unsigned long int)pow(c, d) % n;
    }

private:
    // 求最大公约数
    unsigned long int gcd(unsigned long int a, unsigned long int b)
    {
        if (b == 0)
            return a;
        else
            return gcd(b, a % b);
    }
};

int main()
{
    unsigned long int p, q;
    cout << "请输入两个素数：";
    cin >> p >> q;

    RSA rsa(p, q);
    cout << "公钥：" << rsa.n << "," << rsa.e << endl;
    cout << "私钥：" << rsa.d << endl;

    unsigned long int m;
    cout << "请输入要加密的数字：";
    cin >> m;
    unsigned long int c = rsa.encrypt(m);
    cout << "加密后的数字为：" << c << endl;

    unsigned long int m2 = rsa.decrypt(c);
    cout << "解密后的数字为：" << m2 << endl;

    return 0;
}