Questão 9 - Teorema Chines

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

int mdc(int a, int b) {
if (b == 0)
return a;
return mdc(b, a % b);
}

int inverso_modular(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;

}

int teorema_chines_do_rest(int a[], int n[], int tamanho) {

// Passo 1: Calcular os mdc 
if (mdc(a[0], n[0]) != 1 || mdc(a[1], n[1]) != 1 || mdc(a[2], n[2]) != 1 || mdc(a[3], n[3]) != 1 || 
    mdc(n[0], n[1]) != 1 || mdc(n[0], n[2]) != 1 || mdc(n[0], n[3]) != 1 || mdc(n[1], n[2]) != 1 || mdc(n[1], n[3]) != 1 || mdc(n[2], n[3]) != 1) {
    printf("Não foi possivel calcular devido ao MDC ser diferente de 1 em algum caso.\n");
    exit(1); 
}

// Passo 2: Calcular N
int N = 1;
for (int i = 0; i < tamanho; i++) {
    N *= n[i];
}

int x = 0;

// Passo 3: Calcular Ni
for (int i = 0; i < tamanho; i++) {
    int Ni = N / n[i];
    int yi = inverso_modular(Ni, n[i]);
    x += a[i] * Ni * yi; //Passo 4: Calcular X
}

return x % N; // Passo 5: Retornar X mod N

}

int main() {
int a[4], n[4];
int tamanho = 4;

printf("Informe as equacoes no formato (a[i] mod n[i]):\n");
for (int i = 0; i < tamanho; i++) {
    printf("a[%d]: ", i + 1);
    scanf("%d", &a[i]);
    printf("n[%d]: ", i + 1);
    scanf("%d", &n[i]);
}

int resultado = teorema_chines_do_rest(a, n, tamanho);

printf("A solucao para o sistema de congruencias e: x = %d\n", resultado);

return 0;

}

#Questão 10 - RSA

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

long long potencia_modular(long long base, long long exp, long long mod) {
long long resultado = 1;
base = base % mod;

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

return resultado;

}

void criptografar(char *mensagem, int e, int n, int bloco) {
printf("Mensagem criptografada: ");

for (int i = 0; mensagem[i] != '\0'; i++) {
    int codigo = mensagem[i] - 'A'+1;

    long long criptografado = potencia_modular(codigo, e, n);

    char letra_criptografada = 'A' + (criptografado % 26);

    printf("%c", letra_criptografada);
}

printf("\n");

}

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

printf("Digite p e q: ");
scanf("%d %d", &p, &q);

int n = p * q;  

printf("Digite um numero E: ");
scanf("%d", &e);

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

char mensagem[256];
printf("Digite a mensagem (somente letras maiusculas): ");
scanf("%s", mensagem);

criptografar(mensagem, e, n, bloco);

return 0;

}

#Questão 11 - ISBN e CPF

#include <stdio.h>

int calcular_digito_cpf(int cpf[], int peso_inicial) {
int soma = 0;
for (int i = 0; i < peso_inicial - 1; i++) {
soma += cpf[i] * (peso_inicial - i);
}
int resto = soma % 11;
return (resto < 2) ? 0 : 11 - resto;
}

int calcular_digito_isbn(int isbn[]) {
int soma = 0;
for (int i = 0; i < 9; i++) {
soma += isbn[i] * (i + 1);
}
int resto = soma % 11;
return (resto == 10) ? 'X' : resto;
}

int main() {
int opcao;

printf("1. Calcular CPF completo\n2. Calcular ISBN completo\n");
printf("Opcao: ");
scanf("%d", &opcao);

if (opcao == 1) {
    int cpf[11];

    printf("Digite os 9 primeiros digitos do CPF (sem pontos ou tracos): ");
    for (int i = 0; i < 9; i++) {
        scanf("%1d", &cpf[i]);
    }

    cpf[9] = calcular_digito_cpf(cpf, 10);
    cpf[10] = calcular_digito_cpf(cpf, 11);

    printf("CPF completo: ");
    for (int i = 0; i < 11; i++) {
        printf("%d", cpf[i]);
    }
    printf("\n");

} else if (opcao == 2) {
    int isbn[10];

    printf("Digite os 9 primeiros digitos do ISBN (sem tracos): ");
    for (int i = 0; i < 9; i++) {
        scanf("%1d", &isbn[i]);
    }

    int digito_verificador = calcular_digito_isbn(isbn);

    printf("ISBN completo: ");
    for (int i = 0; i < 9; i++) {
        printf("%d", isbn[i]);
    }
    if (digito_verificador == 'X') {
        printf("X");
    } else {
        printf("%d", digito_verificador);
    }
    printf("\n");

} else {
    printf("Opcao invalida.\n");
}

return 0;

}