#include <stdio.h>
#include <string.h>
#include <math.h>

//Adicionei alguns comentários pra ficar melhor de entender, e pra eu nao me perder tambem no código.

// Função para calcular o Máximo Divisor Comum (MDC) entre dois números
int calcular_mdc(int numero1, int numero2) {
    while (numero2 != 0) {
        int temporario = numero2;
        numero2 = numero1 % numero2;
        numero1 = temporario;
    }
    return numero1;
}

// Função para calcular o inverso modular de um número dado um módulo
int calcular_inverso_modular(int numero, int modulo) {
    int modulo_inicial = modulo, valor_y = 0, valor_x = 1;
    while (numero > 1) {
        int quociente = numero / modulo;
        int temporario = modulo;
        modulo = numero % modulo;
        numero = temporario;
        temporario = valor_y;
        valor_y = valor_x - quociente * valor_y;
        valor_x = temporario;
    }
    if (valor_x < 0)
        valor_x += modulo_inicial;
    return valor_x;
}

// Converte um caractere em um número correspondente
int caractere_para_numero(char caractere) {
    if (caractere >= 'A' && caractere <= 'Z') return caractere - 'A' + 11;
    if (caractere >= 'a' && caractere <= 'z') return caractere - 'a' + 11;
    return -1;
}

// Converte um número em um caractere correspondente
char numero_para_caractere(int codigo) {
    if (codigo >= 11 && codigo <= 36) return 'A' + (codigo - 11);
    return '?';
}

// Calcula a potência modular de forma eficiente
long long calcular_potencia_modular(long long base, long long expoente, long long modulo) {
    long long resultado = 1;
    base = base % modulo;
    while (expoente > 0) {
        if (expoente % 2 == 1)
            resultado = (resultado * base) % modulo;
        expoente = expoente >> 1;
        base = (base * base) % modulo;
    }
    return resultado;
}

int main() {
    // Declaração de variáveis para os números primos, chave pública e tamanho do bloco
    int primo_p, primo_q, chave_publica_e, tamanho_bloco;

    // Entrada dos números primos p e q
    printf("\n--------------------------\n");
    printf("Informe o número primo p: ");
    printf("\n--------------------------\n");
    scanf("%d", &primo_p);
    
    printf("Informe o número primo q: ");
    printf("\n--------------------------\n");
    scanf("%d", &primo_q);

    // Calcula o valor de N (produto de p e q) e Z (totiente de Euler)
    int valor_n = primo_p * primo_q;
    int totiente_z = (primo_p - 1) * (primo_q - 1);
    printf("\n--------------------------\n");
    printf("N = %d\n", valor_n);
    printf("--------------------------\n");
    printf("Z = %d\n", totiente_z);
    printf("--------------------------\n");

    // Entrada da chave pública e tamanho do bloco
    printf("Informe a chave pública E: ");
    scanf("%d", &chave_publica_e);
    printf("Informe o tamanho do bloco: ");
    scanf("%d", &tamanho_bloco);

    // Verifica se a chave pública é coprima de Z
    if (calcular_mdc(chave_publica_e, totiente_z) != 1) {
        printf("Erro: a chave pública E não é coprima de Z(%d).\n", totiente_z);
        return 1;
    }

    // Calcula a chave privada D usando o inverso modular
    int chave_privada_d = calcular_inverso_modular(chave_publica_e, totiente_z);

    printf("Chave pública: (E=%d, N=%d)\n", chave_publica_e, valor_n);
    printf("Chave privada: (D=%d, N=%d)\n", chave_privada_d, valor_n);

    // Entrada da mensagem a ser criptografada
    char mensagem[256];
    printf("Informe a mensagem a ser criptografada (apenas letras): ");
    scanf("%s", mensagem);

    if (strlen(mensagem) == 0) {
        printf("Erro: mensagem vazia.\n");
        return 1;
    }

    // Conversão da mensagem para blocos numéricos
    int blocos_mensagem[256];
    int tamanho_mensagem = strlen(mensagem);

    printf("\nMensagem convertida em blocos:\n");
    for (int i = 0; i < tamanho_mensagem; i++) {
        blocos_mensagem[i] = caractere_para_numero(mensagem[i]);
        if (blocos_mensagem[i] == -1) {
            printf("Erro: a mensagem contém caracteres inválidos.\n");
            return 1;
        }
        printf("%d ", blocos_mensagem[i]);
    }

    // Criptografa cada bloco da mensagem
    printf("\n\nBlocos criptografados:\n");
    long long mensagem_criptografada[256];
    for (int i = 0; i < tamanho_mensagem; i++) {
        mensagem_criptografada[i] = calcular_potencia_modular(blocos_mensagem[i], chave_publica_e, valor_n);
        printf("%lld ", mensagem_criptografada[i]);
    }

    // Descriptografa cada bloco da mensagem criptografada
    printf("\n\nBlocos descriptografados:\n");
    for (int i = 0; i < tamanho_mensagem; i++) {
        int mensagem_descriptografada = calcular_potencia_modular(mensagem_criptografada[i], chave_privada_d, valor_n);
        printf("%c", numero_para_caractere(mensagem_descriptografada));
    }

    printf("\n");
    return 0;
}