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

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int modular_inverse(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;
}

long long modular_exponentiation(long long base, long long exp, long long mod) {
    long long result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1)
            result = (result * base) % mod;
        exp = exp >> 1;
        base = (base * base) % mod;
    }
    return result;
}

void encrypt_message(char *message, int block_size, int e, int n) {
    printf("Mensagem criptografada: ");
    for (int i = 0; i < strlen(message); i++) {
        int value = message[i] - 'A' + 11;
        long long encrypted = modular_exponentiation(value, e, n);
        printf("%lld ", encrypted);
    }
    printf("\n");
}

void decrypt_message(long long *encrypted_blocks, int num_blocks, int d, int n) {
    printf("Mensagem descriptografada: ");
    for (int i = 0; i < num_blocks; i++) {
        long long decrypted = modular_exponentiation(encrypted_blocks[i], d, n);
        char character = (char)(decrypted - 11 + 'A');
        printf("%c", character);
    }
    printf("\n");
}

int main() {
    int p, q, e, block_size;

    printf("Digite dois números primos p e q: ");
    scanf("%d %d", &p, &q);

    int n = p * q;
    int phi = (p - 1) * (q - 1);

    printf("Digite o valor de e (1 < e < phi, coprimo com phi): ");
    scanf("%d", &e);

    if (gcd(e, phi) != 1) {
        printf("Erro: e não é coprimo com phi.\n");
        return 1;
    }

    int d = modular_inverse(e, phi);

    printf("Digite o tamanho do bloco: ");
    scanf("%d", &block_size);

    char message[100];
    printf("Digite a mensagem (apenas letras maiúsculas): ");
    scanf("%s", message);

    encrypt_message(message, block_size, e, n);

    int num_blocks = strlen(message);
    long long encrypted_blocks[num_blocks];
    printf("Digite os blocos criptografados (separados por espaço): ");
    for (int i = 0; i < num_blocks; i++) {
        scanf("%lld", &encrypted_blocks[i]);
    }

    decrypt_message(encrypted_blocks, num_blocks, d, n);

    return 0;
}