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

using namespace std;

// Função para calcular o inverso modular usando o Algoritmo de Euclides Estendido
int modInverse(int a, int m) {
    int m0 = m, t, q;
    int x0 = 0, x1 = 1;
    if (m == 1) return 0;
    while (a > 1) {
        q = a / m;
        t = m;
        m = a % m, a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }
    if (x1 < 0) x1 += m0;
    return x1;
}

// Função para calcular a potência modular
long long modExp(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

// Função para mapear caractere para número baseado em A=11, Z=36, a=37, z=62
int charToNumber(char c) {
    if (c >= 'A' && c <= 'Z') return 11 + (c - 'A');
    if (c >= 'a' && c <= 'z') return 37 + (c - 'a');
    return 0; // Caso inválido
}

// Função para mapear número para caractere
char numberToChar(int num) {
    if (num >= 11 && num <= 36) return 'A' + (num - 11);
    if (num >= 37 && num <= 62) return 'a' + (num - 37);
    return '?'; // Caso inválido
}

// Função para codificar uma string em um vetor de números (blocos para RSA)
vector<int> encodeMessage(const string& message, int n) {
    vector<int> encodedBlocks;
    for (char c : message) {
        int num = charToNumber(c);
        if (!encodedBlocks.empty() && encodedBlocks.back() * 100 + num < n) {
            encodedBlocks.back() = encodedBlocks.back() * 100 + num;  // Junta caracteres no mesmo bloco
        } else {
            encodedBlocks.push_back(num);  // Começa um novo bloco
        }
    }
    return encodedBlocks;
}

// Função para decodificar um vetor de números de volta para string
string decodeMessage(const vector<int>& decryptedBlocks) {
    string message = "";
    for (int block : decryptedBlocks) {
        while (block > 0) {
            int num = block % 100;
            block /= 100;
            message = numberToChar(num) + message;
        }
    }
    return message;
}

int main() {
    int p, q, e;
    cout << "Digite dois números primos (p e q): ";
    cin >> p >> q;
    cout << "Digite o expoente de criptografia (e): ";
    cin >> e;

    int n = p * q;
    int phi = (p - 1) * (q - 1);
    int d = modInverse(e, phi);

    cout << "Chave Pública: (" << e << ", " << n << ")\n";
    cout << "Chave Privada: (" << d << ", " << n << ")\n";

    string inputMessage;
    cout << "Digite uma mensagem (apenas letras, ex: 'Acz'): ";
    cin >> inputMessage;

    vector<int> encodedBlocks = encodeMessage(inputMessage, n);
    vector<int> encryptedBlocks, decryptedBlocks;

    // Criptografia
    for (int block : encodedBlocks) encryptedBlocks.push_back(modExp(block, e, n));

    // Descriptografia
    for (int block : encryptedBlocks) decryptedBlocks.push_back(modExp(block, d, n));

    // Armazena a mensagem descriptografada antes de exibir a criptografada
    string decryptedMessage = decodeMessage(decryptedBlocks);

    // Exibe a mensagem descriptografada antes da criptografada
    cout << "Mensagem Descriptografada: " << decryptedMessage << "\n" << endl;

    // Agora exibe a mensagem criptografada
    cout << "Mensagem Criptografada: ";
    for (int block : encryptedBlocks) cout << block << " ";
    cout << "\n" << endl;

    return 0;
}