Calculadora de Exponenciação Modular

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Protótipos das funções
long long mdc(long long a, long long b);
long long mdc_estendido(long long a, long long b, long long *x, long long *y);
long long inverso_modular(long long a, long long m);
bool eh_primo(long long num);
long long exponenciacao_modular(long long base, long long expoente, long long mod);
long long funcao_totiente_euler(long long n);
void imprimir_passo(const char *mensagem, long long valor);

int main() {
long long H, G, n, x, n1;

printf("===== Calculadora de Exponenciação Modular =====\n");
printf("Este programa demonstra os processo para calcular a^x mod n1\n");
printf("Onde 'a' é definido como (H ⊘ G) em Zn (H dividido por G módulo n)\n\n");

// Entrada de valores com explicações
printf("Digite os valores um por um:\n");
printf("Digite o valor de H (numerador para calcular a base): ");
scanf("%lld", &H);
printf("Digite o valor de G (denominador para calcular a base): ");
scanf("%lld", &G);
printf("Digite o valor de n (módulo para a divisão H/G): ");
scanf("%lld", &n);
printf("Digite o valor do expoente x: ");
scanf("%lld", &x);
printf("Digite o valor do módulo n1 (para a^x mod n1): ");
scanf("%lld", &n1);

printf("\n===== Passo 1: Verificar se 'G' e 'n' são coprimos =====\n");
long long g = mdc(G, n);
if (g != 1) {
    printf("'G' e 'n' não são coprimos (mdc(%lld, %lld) = %lld). Divisão não é possível em Z_%lld.\n", G, n, g, n);
    printf("O programa não pode continuar. Saindo...\n");
    return 1;
}
printf("'G' e 'n' são coprimos (mdc(%lld, %lld) = 1). Divisão é possível em Z_%lld.\n", G, n, n);

printf("\n===== Passo 2: Calcular o inverso de 'G' em Zn =====\n");
long long G_inv = inverso_modular(G, n);
if (G_inv == -1) {
    printf("Inverso de 'G' não existe em Z_%lld. Isso contradiz o resultado do passo 1.\n", n);
    printf("O programa não pode continuar. Saindo...\n");
    return 1;
}
printf("O inverso de %lld em Z_%lld é %lld\n", G, n, G_inv);

printf("\n===== Passo 3: Calcular a = H/G em Zn =====\n");
long long a = (H * G_inv) % n;
printf("a = (H * G^-1) mod n = (%lld * %lld) mod %lld = %lld\n", H, G_inv, n, a);

printf("\n===== Passo 4: Verificar se 'a' e n1 são coprimos =====\n");
long long mdc_a_n1 = mdc(a, n1);
if (mdc_a_n1 != 1) {
    printf("'a' e n1 não são coprimos (mdc(%lld, %lld) = %lld).\n", a, n1, mdc_a_n1);
} else {
    printf("'a' e n1 são coprimos (mdc(%lld, %lld) = 1).\n", a, n1);
}

printf("\n===== Passo 5: Verificar se n1 é primo =====\n");
bool n1_primo = eh_primo(n1);
if (n1_primo) {
    printf("%lld é um número primo.\n", n1);
} else {
    printf("%lld não é um número primo.\n", n1);
}

printf("\n===== Passo 6/7: Determinar a redução do expoente =====\n");
long long expoente_reduzido;
if (n1_primo) {
    expoente_reduzido = n1 - 1;
    printf("Como n1 é primo, podemos aplicar o Pequeno Teorema de Fermat.\n");
    printf("Expoente reduzido: x mod (n1-1) = %lld mod %lld\n", x, expoente_reduzido);
} else {
    expoente_reduzido = funcao_totiente_euler(n1);
    printf("Como n1 não é primo, aplicamos o Teorema de Euler.\n");
    printf("Função totiente de Euler φ(%lld) = %lld\n", n1, expoente_reduzido);
    printf("Expoente reduzido: x mod φ(n1) = %lld mod %lld\n", x, expoente_reduzido);
}
long long x_mod = x % expoente_reduzido;
printf("Valor do expoente reduzido: %lld mod %lld = %lld\n", x, expoente_reduzido, x_mod);

printf("\n===== Passo 8: Decompor o expoente x =====\n");
long long q = expoente_reduzido;
long long x1 = x / q;
long long r = x % q;
printf("Usando o teorema da divisão: \n x = x1*q + r \n x = %lld*%lld + %lld\n x = %lld\n", x1, q, r, x1*q+r);

printf("\n===== Passo 9: Reescrever a expressão =====");
printf("\na^x mod n1 = ((a^(x1*q) mod n1) * (a^r mod n1)) mod n1\n");
printf("            = (( (a^x1 mod n1)^q mod n1 ) * (a^r mod n1)) mod n1\n");

printf("\n===== Passo 10: Calcular valores intermediários =====\n");
long long a_x1_mod = exponenciacao_modular(a, x1, n1);
printf("a^x1 mod n1 = %lld^%lld mod %lld = %lld\n", a, x1, n1, a_x1_mod);

long long x2_q_mod = exponenciacao_modular(a_x1_mod, q, n1);
printf("(a^x1)^q mod n1 = %lld^%lld mod %lld = %lld\n", a_x1_mod, q, n1, x2_q_mod);

long long a_r_mod = exponenciacao_modular(a, r, n1);
printf("a^r mod n1 = %lld^%lld mod %lld = %lld\n", a, r, n1, a_r_mod);

printf("\n===== Passo 11: Combinar resultados para a resposta final =====\n");
long long resultado = (x2_q_mod * a_r_mod) % n1;
printf("Resultado final: (%lld * %lld) mod %lld = %lld\n", x2_q_mod, a_r_mod, n1, resultado);

printf("\n===== Resposta Final =====\n");
printf("%lld^%lld mod %lld = %lld\n", a, x, n1, resultado);

return 0;

}

// Função para calcular máximo divisor comum (MDC) usando algoritmo de Euclides
long long mdc(long long a, long long b) {
while (b != 0) {
long long temp = b;
b = a % b;
a = temp;
}
return a;
}

// Algoritmo de Euclides Estendido para encontrar inverso modular
long long mdc_estendido(long long a, long long b, long long *x, long long *y) {
if (a == 0) {
*x = 0;
*y = 1;
return b;
}

long long x1, y1;
long long gcd = mdc_estendido(b % a, a, &x1, &y1);

*x = y1 - (b / a) * x1;
*y = x1;

return gcd;

}

// Função para encontrar inverso modular usando Euclides Estendido
long long inverso_modular(long long a, long long m) {
long long x, y;
long long g = mdc_estendido(a, m, &x, &y);
if (g != 1) {
return -1; // inverso não existe
} else {
// Garantir que o resultado é positivo
return (x % m + m) % m;
}
}

// Teste de Miller-Rabin para verificar primalidade
bool teste_miller_rabin(long long d, long long n) {
long long a = 2 + rand() % (n - 4);
long long x = exponenciacao_modular(a, d, n);

if (x == 1 || x == n - 1) return true;

while (d != n - 1) {
    x = (x * x) % n;
    d *= 2;
    
    if (x == 1) return false;
    if (x == n - 1) return true;
}

return false;

}

// Função para verificar se um número é primo (usando teste de Miller-Rabin)
bool eh_primo(long long num) {
if (num <= 1) return false;
if (num <= 3) return true;
if (num % 2 == 0) return false;

long long d = num - 1;
while (d % 2 == 0) d /= 2;

// Testar com k=5 iterações (suficiente para números até 2^64)
for (int i = 0; i < 5; i++) {
    if (!teste_miller_rabin(d, num)) return false;
}

return true;

}

// Função para exponenciação modular (potenciação eficiente módulo mod)
long long exponenciacao_modular(long long base, long long expoente, long long mod) {
long long resultado = 1;
base = base % mod;

while (expoente > 0) {
    if (expoente % 2 == 1) {
        resultado = (resultado * base) % mod;
    }
    expoente = expoente >> 1;
    base = (base * base) % mod;
}

return resultado;

}

// Função para calcular a função totiente de Euler φ(n)
long long funcao_totiente_euler(long long n) {
if (n == 1) return 1;
if (eh_primo(n)) return n - 1;

long long resultado = n;

// Verificar divisibilidade por 2
if (n % 2 == 0) {
    resultado -= resultado / 2;
    while (n % 2 == 0) n /= 2;
}

// Verificar divisores ímpares até sqrt(n)
for (long long i = 3; i * i <= n; i += 2) {
    if (n % i == 0) {
        resultado -= resultado / i;
        while (n % i == 0) n /= i;
    }
}

// Se n restante for um primo maior que 2
if (n > 1) {
    resultado -= resultado / n;
}

return resultado;

}