Atividade 2 - P2 - 200043030

Atividade 2 - Matemática Discreta II P2 - 200043030

Q9 - Teorema Chines

https://onecompiler.com/c/436s2v5x9

Input:
4 --> Quant. de equações
2 3 --> Eq. linear 1 (onde 2 é "a" e 3 é "b", sendo equivalente a "x ≡ 2 mod 3")
5 7 --> Eq. linear 2 (seguindo a mesma regra acima)
13 5 --> Eq. linear 3
2 11 --> Eq. linear 4

Q10 - Cript RSA

https://onecompiler.com/c/436s3n8cd

Input:
5 3 3 1
ALMOCO BOM

O valores de "p", "q", "e", "tamanho do bloco" são inputados em série separados por espaço
A frase que deve ser codificado é inserida logo em seguida

Q11 - Calcula CPF e ISBN

https://onecompiler.com/c/436s4kk58

Input:
017869481
056394422
978123456789

Os primeiros 9 números formadores de um CPF
Os primeiros 9 números de um ISBN10
Os primeiros 12 números de um ISBN13

Todos os scripts estão no OneCompiler com a visibilidade como "Public", os scripts já estão com inputs de exemplo, mas caso seja necessário esse input poderá ser alterado desde que seja um input válido.

O script de cada solução pode ser encontrado logo a baixo:

Q9 - Teorema Chines

#include <stdlib.h>

typedef struct {
    int a;
    int n;
} Congruence;

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

int extended_gcd(int a, int b, int *x, int *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }
    int x1, y1;
    int g = extended_gcd(b, a % b, &x1, &y1);
    *x = y1;
    *y = x1 - (a / b) * y1;
    return g;
}

int chinese_remainder_theorem(Congruence *congruences, int size) {
    int N = 1;
    for (int i = 0; i < size; i++) {
        N *= congruences[i].n;
    }

    int x = 0;
    for (int i = 0; i < size; i++) {
        int a_i = congruences[i].a;
        int n_i = congruences[i].n;
        int N_i = N / n_i;
        int m_i, y;
        int g = extended_gcd(N_i, n_i, &m_i, &y);
        if (g != 1) {
            // Os módulos não são coprimos
            return -1;
        }
        int e_i = (m_i % n_i + n_i) % n_i;
        x += a_i * e_i * N_i;
    }

    return (x % N + N) % N;
}

int main() {
    printf("Digite o número de tuplas (máximo 4):\n");
    int size;
    scanf("%d", &size);

    if (size < 1 || size > 4) {
        printf("Número inválido de tuplas. Deve ser entre 1 e 4.\n");
        return 1;
    }

    Congruence congruences[4];
    printf("Digite as tuplas no formato a n (separadas por espaço):\n");
    for (int i = 0; i < size; i++) {
        if (scanf("%d %d", &congruences[i].a, &congruences[i].n) != 2) {
            printf("Entrada inválida. Certifique-se de fornecer pares de inteiros no formato correto.\n");
            return 1;
        }
    }

    printf("O sistema de congruências inserido é:\n");
    for (int i = 0; i < size; i++) {
        printf("x ≡ %d mod %d\n", congruences[i].a, congruences[i].n);
    }

    int solution = chinese_remainder_theorem(congruences, size);
    int N = 1;
    for (int i = 0; i < size; i++) {
        N *= congruences[i].n;
    }

    if (solution != -1) {
        printf("A solução do sistema de congruências é x ≡ %d mod %d\n", solution, N);
    } else {
        printf("Os módulos fornecidos não são coprimos e o sistema não pode ser resolvido.\n");
    }

    return 0;
}

Q10 - Cript RSA

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

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

int inverso_modular(int a, int m) {
    a = a % m;
    for (int x = 1; x < m; x++) {
        if ((a * x) % m == 1) {
            return x;
        }
    }
    return -1; 
}

int exp_modular(int base, int exp, int mod) {
    int 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 tamanho_bloco) {
    char alfabeto[27] = {0}; 
    int index = 0;
    
    for (int i = 0; i < 26; i++) {
        alfabeto[i] = 11 + i;
    }

    int espaco = 0;

    printf("Mensagem original: %s\n", mensagem);
    printf("Mensagem criptografada:\n");
    for (int i = 0; mensagem[i] != '\0'; i++) {
        if (mensagem[i] == ' ') {
            printf("%d ", espaco);
        } else {
            for (int j = 0; j < 26; j++) {
                if (mensagem[i] == 'A' + j) {
                    index = alfabeto[j];
                    break;
                }
            }
            int criptografado = exp_modular(index, e, n);
            printf("%d ", criptografado);
        }
    }
    printf("\n");
}

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

    printf("Digite os valores para p, q, e e o tamanho do bloco:\n");
    printf("p (primo): \n");
    scanf("%d", &p);
    printf("q (primo): \n");
    scanf("%d", &q);
    printf("e: \n");
    scanf("%d", &e);
    printf("Tamanho do bloco: \n");
    scanf("%d", &tamanho_bloco);

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

    if (mdc(e, fi_n) != 1) {
        printf("Erro: 'e' deve ser coprimo de phi(n).\n");
        return 1;
    }

    char mensagem[100];
    printf("Digite a mensagem a ser criptografada (letras maiúsculas e espaços): ");
    getchar();
    fgets(mensagem, sizeof(mensagem), stdin);

    criptografar(mensagem, e, n, tamanho_bloco);

    return 0;
}

Q11 - Calcula CPF e ISBN

#include <stdio.h>

int calcular_dv_cpf(int cpf[], int n) {
    int peso[] = {10, 9, 8, 7, 6, 5, 4, 3, 2};
    int soma = 0;
    for (int i = 0; i < n; i++) {
        soma += cpf[i] * peso[i];
    }
    int resto = soma % 11;
    return (resto < 2) ? 0 : 11 - resto;
}

int calcular_dv2_cpf(int cpf[], int n) {
    int peso[] = {11, 10, 9, 8, 7, 6, 5, 4, 3, 2};
    int soma = 0;
    for (int i = 0; i < n; i++) {
        soma += cpf[i] * peso[i];
    }
    int resto = soma % 11;
    return (resto < 2) ? 0 : 11 - resto;
}

void calcular_cpf(long long cpf) {
    int cpf_array[9];
    
    for (int i = 8; i >= 0; i--) {
        cpf_array[i] = cpf % 10;
        cpf /= 10;
    }
    
    int dv1 = calcular_dv_cpf(cpf_array, 9);
    cpf_array[9] = dv1;
    int dv2 = calcular_dv2_cpf(cpf_array, 10);
    
    printf("CPF: ");
    for (int i = 0; i < 9; i++) {
        printf("%d", cpf_array[i]);
    }
    printf(" - %d%d\n", dv1, dv2);
}

int calcular_dv_isbn10(int isbn[], int n) {
    int soma = 0;
    for (int i = 0; i < n; i++) {
        soma += isbn[i] * (10 - i);
    }
    int resto = soma % 11;
    return (resto == 0) ? 0 : 11 - resto;
}

int calcular_dv_isbn13(int isbn[], int n) {
    int soma = 0;
    for (int i = 0; i < n; i++) {
        soma += isbn[i] * (i % 2 == 0 ? 1 : 3);
    }
    int resto = soma % 10;
    return (resto == 0) ? 0 : 10 - resto;
}

void calcular_isbn10(long long isbn10) {
    int isbn_array[9];
    
    for (int i = 8; i >= 0; i--) {
        isbn_array[i] = isbn10 % 10;
        isbn10 /= 10;
    }
    
    int dv = calcular_dv_isbn10(isbn_array, 9);
    
    printf("ISBN-10: ");
    for (int i = 0; i < 9; i++) {
        printf("%d", isbn_array[i]);
    }
    printf(" - %d\n", dv);
}

void calcular_isbn13(long long isbn13) {
    int isbn_array[12];
    
    for (int i = 11; i >= 0; i--) {
        isbn_array[i] = isbn13 % 10;
        isbn13 /= 10;
    }
    
    int dv = calcular_dv_isbn13(isbn_array, 12);
    
    printf("ISBN-13: ");
    for (int i = 0; i < 12; i++) {
        printf("%d", isbn_array[i]);
    }
    printf(" - %d\n", dv);
}

int main() {
    long long cpf, isbn10, isbn13;
    
    printf("Digite os 9 primeiros dígitos do CPF (apenas números): \n");
    scanf("%lld", &cpf);
    calcular_cpf(cpf);
    
    printf("Digite os 9 primeiros dígitos do ISBN-10 (apenas números): \n");
    scanf("%lld", &isbn10);
    calcular_isbn10(isbn10);
    
    printf("Digite os 12 primeiros dígitos do ISBN-13 (apenas números): \n");
    scanf("%lld", &isbn13);
    calcular_isbn13(isbn13);
    
    return 0;
}