OneCompiler

Lista 2 - MD2

116

Lista 2

Aluno: Gabriel Lima da Silva
Matrícula: 222037610
Linguagem: C
Link no final!

9 - Teorema Chines do Resto

#include <stdio.h>

// Função para calcular o MDC
int mdc(int a, int b) {
    if (b == 0) {
      return a;
    }
    return mdc(b, a % b); // recursao mdc
}

// Função para calcular o inverso modular de "a" módulo "m"
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 é o quociente
        q = a / m;
        t = m;

        // m é o resto agora
        m = a % m;
        a = t;
        t = x0;

        x0 = x1 - q * x0;
        x1 = t;
    }

    // Ajusta x1 para ser positivo
    if (x1 < 0)
        x1 += m0;

    return x1;
}

int main() {
    int n;

    printf("Ola professora! Digite o numero de equacoes (maximo 4):\n");
    scanf("%d", &n);

    if (n < 1 || n > 4) {
        printf("Numero de equacoes invalido! Por favor, digite novamente.\n");
        return 1;
    }

    // vetores para armazenar os restos e módulos das equações
    int restos[4], modulos[4];

    for (int i = 0; i < n; i++) {
        printf("Digite o resto r%d e o modulo m%d, respectivamente:\n", i + 1, i + 1);
        scanf("%d %d", &restos[i], &modulos[i]);
    }

    // Verifica se os módulos são coprimos dois a dois
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (mdc(modulos[i], modulos[j]) != 1) {
                printf("Os modulos não são coprimos dois a dois!\n");
                return 1;
            }
        }
    }

    // Calcula o produto total dos módulos -> x mod M
    int M = 1;
    for (int i = 0; i < n; i++) {
        M *= modulos[i];
    }

    // Calcula a solução usando o Teorema Chinês do Resto
    int x = 0; // X = C*N*Y+...
    for (int i = 0; i < n; i++) {
        int Mi = M / modulos[i];
        int inv = inverso_modular(Mi, modulos[i]);
        x += restos[i] * Mi * inv;
    }

    // Ajusta x para o intervalo [0, M)
    x = (x % M + M) % M;

    printf("Sua solucao:\nx = %d (mod %d)\n", x, M);

    return 0;
}

10 - RSA

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

// Função para verificar se um número é primo
int ehPrimo(int num) {
    if (num < 2) return 0;
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) return 0;
    }
    return 1;
}

// Função para calcular o MDC
int mdc(int a, int b) {
    if (b == 0) {
      return a;
    }
    return mdc(b, a % b); // recursao mdc
}

// Função para calcular o inverso modular de "a" módulo "m"
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 é o quociente
        q = a / m;
        t = m;

        // m é o resto agora
        m = a % m;
        a = t;
        t = x0;

        x0 = x1 - q * x0;
        x1 = t;
    }

    // Ajusta x1 para ser positivo
    if (x1 < 0)
        x1 += m0;

    return x1;
}

// Função para realizar a exponenciação modular
long long exponenciacaoModular(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; // Divisão inteira por 2
        base = (base * base) % mod;
    }
    return resultado;
}

void codificar_palavra(const char *texto, int *codigo, int tamanho) {
    for (int i = 0; i < tamanho; i++) {
        if (texto[i] >= 'A' && texto[i] <= 'Z') {
            codigo[i] = 11 + (texto[i] - 'A'); // A - Z
        } else if (texto[i] == ' ') {
            codigo[i] = 37; // espaço
        } else {
            codigo[i] = 0; // invalido
        }
    }   
}

void criptografar_palavra(int *texto, int tam, int e, int n, int *criptografada) {
    for (int i = 0; i < tam; i++) {
        long long resultado = 1;
        int base = texto[i];
        int exp = e;

        while (exp > 0) {
            if (exp % 2 == 1) {
                resultado = (resultado * base) % n;
            }
            base = (base * base) % n;
            exp /= 2;
        }
        criptografada[i] = (int)resultado;
    }
}
int main() {
    int p, q, e;
    char palavra[100];

    // Entrada dos números primos p e q
    do {
        printf("Digite os numeros primos p e q, respectivamente:\n");
        scanf("%d %d", &p, &q);
        if (!ehPrimo(p) || !ehPrimo(q)) {
            printf("Ambos os numeros devem ser primos. Tente novamente.\n");
        }
    } while (!ehPrimo(p) || !ehPrimo(q));

    // Calculando n e φ(n)
    int n = p * q;
    int phi = (p - 1) * (q - 1);

    // Entrada do número E
    do {
        printf("Digite o numero E (deve ser coprimo com (n) = %d): ", phi);
        scanf("%d", &e);
        if (mdc(e, phi) != 1) {
            printf("E deve ser coprimo com (n). Tente novamente.\n");
        }
    } while (mdc(e, phi) != 1);

    // Calculando D (inverso modular de E)
    int d = inverso_modular(e, phi);
    if (d == -1) {
        printf("Nao foi possível calcular o inverso modular de E.\n");
        return 1;
    }

    // Entrada da palavra a ser criptografada
    printf("Digite a palavra a ser criptografada (apenas letras maiusculas): ");
    scanf("%s", palavra);

    // tamanho da palavra 
    int tamanhoPalavra = strlen(palavra);
    int palavraCodigo[256];
    codificar_palavra(palavra, palavraCodigo, tamanhoPalavra);

    // Criptografia
    int criptografado[256];
    criptografar_palavra(palavraCodigo, tamanhoPalavra, e, n, criptografado);

    printf("Criptografando...\n");
    for(int i = 0; i < tamanhoPalavra; i++) {
        printf("%d ", criptografado[i]);
    }
    printf("\n");

    // Exibindo chaves
    printf("Chave publica: (E = %d, N = %d)\n", e, n);
    printf("Chave privada: (D = %d, N = %d)\n", d, n);

    return 0;
}

11 - CPF e ISBN

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

// Função para calcular o dígito verificador do CPF
int calcularDigitoCPF(const int cpf[], int pesoInicial) {
    int soma = 0;
    for (int i = 0; i < pesoInicial - 1; i++) {
        soma += cpf[i] * (pesoInicial - i);
    }
    int resto = soma % 11;
    return (resto < 2) ? 0 : 11 - resto;
}

// Função para validar um CPF e exibir os dígitos verificadores calculados
int validarCPF(const char* cpfStr) {
    int cpf[11];
    if (strlen(cpfStr) != 11) return 0;

    for (int i = 0; i < 11; i++) {
        if (!isdigit(cpfStr[i])) return 0;
        cpf[i] = cpfStr[i] - '0';
    }

    int digito1 = calcularDigitoCPF(cpf, 10);
    int digito2 = calcularDigitoCPF(cpf, 11);

    printf("Digito verificador 1 calculado: %d\n", digito1);
    printf("Digito verificador 2 calculado: %d\n", digito2);

    return digito1 == cpf[9] && digito2 == cpf[10];
}

// Função para calcular o dígito verificador do ISBN-10
char calcularDigitoISBN(const 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 + '0';
}

// Função para validar um ISBN-10 e exibir o dígito verificador calculado
int validarISBN(const char* isbnStr) {
    int isbn[10];
    if (strlen(isbnStr) != 10) return 0;

    for (int i = 0; i < 9; i++) {
        if (!isdigit(isbnStr[i])) return 0;
        isbn[i] = isbnStr[i] - '0';
    }

    char digitoVerificadorCalculado = calcularDigitoISBN(isbn);
    printf("Digito verificador calculado: %c\n", digitoVerificadorCalculado);

    return digitoVerificadorCalculado == isbnStr[9];
}

int main() {
    // Exemplo de CPF
    char cpf[12];
    printf("Ola professora! Bem vinda ao verificador de CPF e ISBN.\n");
    printf("Digite um CPF (somente numeros): ");
    scanf("%11s", cpf);

    if (validarCPF(cpf)) {
        printf("CPF valido!\n");
    } else {
        printf("CPF invalido!\n");
    }

    // Exemplo de ISBN-10
    char isbn[11];
    printf("Digite um ISBN-10 (9 numeros + digito verificador): ");
    scanf("%10s", isbn);

    if (validarISBN(isbn)) {
        printf("ISBN valido!\n");
    } else {
        printf("ISBN invalido!\n");
    }

    return 0;
}

9- https://onecompiler.com/c/4369phrxn
10- https://onecompiler.com/c/4369qys4h
11- https://onecompiler.com/c/4369r4kvs