Primeira Prova

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

typedef long long ll;

ll calcular_mdc(ll a, ll b) {
while (b != 0) {
ll temp = b;
b = a % b;
a = temp;
}
return a;
}

ll multiplicacao_modular(ll a, ll b, ll mod) {
ll resultado = 0;
a = a % mod;
while (b > 0) {
if (b % 2 == 1)
resultado = (resultado + a) % mod;
a = (a * 2) % mod;
b = b / 2;
}
return resultado % mod;
}

ll inverso_modular(ll G, ll n) {
ll t = 0, novo_t = 1;
ll r = n, novo_r = G;

while (novo_r != 0) {
    ll quociente = r / novo_r;
    
    ll temp_t = novo_t;
    novo_t = t - quociente * novo_t;
    t = temp_t;
    
    ll temp_r = novo_r;
    novo_r = r - quociente * novo_r;
    r = temp_r;
}

if (r > 1) return -1;
if (t < 0) t = t + n;

return t;

}

ll exponenciacao_modular(ll base, ll expoente, ll mod) {
ll resultado = 1;
base = base % mod;

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

return resultado;

}

int verificar_primo(ll n) {
if (n <= 1) return 0;
if (n <= 3) return 1;
if (n % 2 == 0 || n % 3 == 0) return 0;

for (ll i = 5; i * i <= n; i += 6) {
    if (n % i == 0 || n % (i + 2) == 0)
        return 0;
}
return 1;

}

ll funcao_totiente_euler(ll n) {
ll resultado = n;

for (ll p = 2; p * p <= n; ++p) {
    if (n % p == 0) {
        while (n % p == 0)
            n = n / p;
        resultado -= resultado / p;
    }
}

if (n > 1)
    resultado -= resultado / n;

return resultado;

}

void limpar_buffer() {
while (getchar() != '\n');
}

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

printf("Sistema de Verificacao Modular\n");


printf("Digite o valor de H (numerador): ");
while (scanf("%lld", &H) != 1 || H < 1) {
    printf("Entrada invalida! Digite um inteiro positivo: ");
    limpar_buffer();
}

printf("Digite o valor de G (denominador): ");
while (scanf("%lld", &G) != 1 || G < 1) {
    printf("Entrada invalida! Digite um inteiro positivo: ");
    limpar_buffer();
}

printf("Digite o valor de n (modulo para Zn): ");
while (scanf("%lld", &n) != 1 || n < 2) {
    printf("Entrada invalida! Digite um inteiro >= 2: ");
    limpar_buffer();
}

printf("Digite o valor de x (expoente): ");
while (scanf("%lld", &x) != 1 || x < 0) {
    printf("Entrada invalida! Digite um inteiro nao negativo: ");
    limpar_buffer();
}

printf("Digite o valor de n1 (modulo final): ");
while (scanf("%lld", &n1) != 1 || n1 < 1) {
    printf("Entrada invalida! Digite um inteiro positivo: ");
    limpar_buffer();
}


printf("\nVerificando se G e n sao coprimos...\n");
ll mdc_gn = calcular_mdc(G, n);
if (mdc_gn != 1) {
    printf("ERRO: G e n nao sao coprimos (MDC = %lld). Divisao impossivel!\n", mdc_gn);
    return 0;
}
printf("OK: G e n sao coprimos (MDC = 1)\n");

printf("\nCalculando inverso modular de G em Zn...\n");
ll inverso_G = inverso_modular(G, n);
if (inverso_G == -1) {
    printf("ERRO: Inverso modular nao existe!\n");
    return 0;
}
printf("Inverso modular de G: %lld\n", inverso_G);

printf("\nCalculando a = (H * G⁻¹) mod n...\n");
ll a = multiplicacao_modular(H % n, inverso_G % n, n);
printf("a = (%lld * %lld) mod %lld = %lld\n", H, inverso_G, n, a);

printf("\nVerificando se a e n1 sao coprimos...\n");
ll mdc_an1 = calcular_mdc(a, n1);
if (mdc_an1 != 1) {
    printf("AVISO: a e n1 nao sao coprimos (MDC = %lld). Resultado pode ser incorreto!\n", mdc_an1);
} else {
    printf("OK: a e n1 sao coprimos (MDC = 1)\n");
}

printf("\nVerificando se n1 e primo...\n");
int primo = verificar_primo(n1);
printf("n1 %s primo\n", primo ? "e" : "nao e");

printf("\nCalculando x1...\n");
ll x1 = primo ? n1 - 1 : funcao_totiente_euler(n1);
printf("x1 = %s ? %lld-1 : φ(%lld) = %lld\n", 
       primo ? "primo" : "composto", n1, n1, x1);

printf("\nDecompondo o expoente x...\n");
ll q = x / x1;
ll r = x % x1;
printf("x = %lld = %lld*%lld + %lld\n", x, x1, q, r);

printf("\nCalculando valores intermediarios:\n");
ll x2 = exponenciacao_modular(a, x1, n1);
printf("a^x1 mod n1 = %lld^%lld mod %lld = %lld\n", a, x1, n1, x2);

ll x2q = exponenciacao_modular(x2, q, n1);
printf("(a^x1)^q mod n1 = %lld^%lld mod %lld = %lld\n", x2, q, n1, x2q);

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

printf("\nCombinando resultados:\n");
ll resultado = multiplicacao_modular(x2q, ar, n1);
printf("Resultado final = (%lld * %lld) mod %lld = %lld\n", x2q, ar, n1, resultado);

printf("\nResultado Final, então tudo deu certo!!!\n");
printf("%lld^%lld mod %lld ≡ %lld\n", a, x, n1, resultado);

return 0;

}