RSA

#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
typedef long long int lli;
typedef pair<lli, pair<lli, lli>> pai;
lli p, q, n, euler_num, e, d, m, c, rc;
void choose_public_key(lli k) {
    for (int i = 2; i < k; i++) {
        bool flag = 0;
        for (int g = 2; g <= i; g++) {
            if (i % g == 0 && k % g == 0) flag=1;
        }
        if (!flag) cout << i << " ";
    }
    cout << "\n";
}
pai xGCD(lli a, lli b) {
    if (b == 0) return { a,{1,0} };
    pai ret = xGCD(b, a % b);
    lli g, x, y;
    g = ret.first;
    tie(x, y) = ret.second;
    return { g,{y,x - (a / b) * y} };
}
lli mod_inverse(lli a, lli mod) {
    auto res = xGCD(a, mod);
    if (res.first > 1) return -1;
    return (res.second.first + mod) % mod;
}
lli power_by_divide_and_conquer(lli a, lli b, lli c) {
    lli tmp = 1;
    while (b) {
        if (b & 1) tmp = tmp * a % c;
        b /= 2;
        a = a * a % c;
    }
    return tmp;
}
lli RSA_Encryption() {
    return power_by_divide_and_conquer(m, e, n);
}
lli RSA_Decryption() {
    return power_by_divide_and_conquer(c, d, n);
}
int main() {
    fastio;
    cout << "input your prime num :";
    cin >> p >> q;
    n = p * q; euler_num = (p - 1) * (q - 1);
    choose_public_key(euler_num);
    cout << "choose your public key from above: ";
    cin >> e;
    d = mod_inverse(e, euler_num);
    cout << "your private key :" << d << "\n";
    cout << "****************************\n";
    cout << "your base setting\n";
    cout << "p :" << p << " q :" << q << " n :" << n << " euler_num :" << euler_num << " e :" << e << " d :" << d << "\n";
    cout << "input your message :";
    cin >> m;
    c = RSA_Encryption();
    cout << c << "\n";
    rc = RSA_Decryption();
    cout << "****************************\n";
    cout << "plain text :" << m << " RSA_Encryption :" << c << " RSA_Decryption :" << rc << "\n";
}