URI (BEECROWD) - 2636 - 3-RSA - Matemática - C, C++ e Haskell

Vamos resolver um probleminha bem difícil do Beecrowd! Pelo menos em comparação com os que estamos acostumados. O problema 3-RSA vale 9,1 pontos na plataforma. Mas falando sério, tem problemas que considero bem mais difíceis... enfim, o fato é que o problema está resolvido e que aqui ele será apresentado a vocês!

Plataforma: URI (BEECROWD)

Problema: 2636

Linguagens: C, C++ e Haskell

Enunciado:

Pedro, assim como muitos outros estudantes de graduação, ficou fascinado com a beleza e sofisticação da criptografia. Começou a ler referências históricas, estudar os principais algoritmos e a buscar artigos e reportagens que abordassem o tema sob os mais diferentes aspectos.

Contudo, o grande volume de informações adquiridas num curto espaço de tempo o levou a alguns questionamentos e temores. Preocupado com a computação quântica, que em teoria inutilizaria a criptografia RSA, e motivado pela história do algoritmo DES, que teve uma evolução mais segura denominada 3DES, ele resolveu propôr uma versão mais segura do RSA, denominada 3-RSA.

No 3-RSA, o módulo n, composto no algoritmo original por dois números primos ı́mpares distintos, seria agora composto por 3 primos ı́mpares distintos! Pedro estava certo que esta modificação traria maior dificuldade de quebra do algoritmo, uma vez que os atacantes agora teriam que encontrar 3 fatores de n, e não apenas 2.

Sabendo que, em criptografia, às vezes menos é mais, e disposto a mostrar ao motivado e bem intencionado Pedro que a modificação proposta, de fato, enfraquece o RSA, fatore o módulo n do algoritmo 3-RSA, exibindo seus três fatores primos.

Solução:

A estratégia é utilizar o crivo de eratóstenes para preencher o array primos, assim facilitando a fatoração do número informado (n). Com isso, varrendo o array de primos encontra-se tanto p quanto q. Tendo esses valores e n, fica fácil obter r, pois ele será n/(p*q).

Código em C:

#include <stdio.h> 

int main() { 
    int max = 1000000;
    int i;
    int primos[max+1];
    long long int n;
    long long int p;
    long long int q;

    for (i = 1; i <= max; i += 2)
        primos[i] = 1;

    for (i = 0; i <= max; i += 2)
        primos[i] = 0;

    for (i = 3; i * i <= max; i += 2) {
        if (primos[i]) {
            for (int j = i * i; j <= max; j += i)
                primos[j] = 0;
        }
    }

    while (1) {
        scanf("%lld", &n);
        if (!n)
            return 0;
        for (i = 3; i <= max; i += 2) {
            if (primos[i] && n % i == 0) {
                p = i;
                break;
            }
        }     
        for (i = p + 2; i <= max; i += 2) {
            if (primos[i] && n % i == 0) {
                q = i;
                break;
            }
        }
        long long int r = n / (p * q);
        printf("%lld = %lld x %lld x %lld\n", n, p, q, r);
    }
    return 0; 
}

Código em C++:

A solução segue a mesma lógica do código C.

#include <bits/stdc++.h> 

using namespace std; 

int main() {   
    int max = 1000000;
    int i;
    long long int n;
    long long int p;
    long long int q;
    bool* primos = new bool[max + 1]; 

    for (i = 1; i <= max; i += 2)
        primos[i] = true;
     
    for (i = 0; i <= max; i += 2)
        primos[i] = false;     

    for (i = 3; i * i <= max; i += 2) {
        if (primos[i]) {
            for (int j = i * i; j <= max; j += i)
                primos[j] = false;
        }
    }
    
    while (cin >> n) {    
        if (!n)
            return 0;         

        for (i = 3; i <= max; i += 2) {
            if (primos[i] && n % i == 0) {
                p = i;
                break;
            }
        }
        
        for (i = p + 2; i <= max; i += 2) {
            if (primos[i] && n % i == 0) {
                q = i;
                break;
            }
        }       
        long long int r = n / (p * q);
        cout << n << " = " << p << " x " << q << " x " << r << endl;
    }
    return 0; 
}

Código em Haskell:

Aqui eu acabei nem fazendo o crivo, pois o número será encontrado de qualquer forma (sabe-se que ele é o produto de três primos). O que fiz foi iterar a função findTerm partindo do 3 e somando sempre 2 (ou seja, procurando ímpares). Essa solução passou no beecrowd.

main :: IO ()
main =  do
   n <- readLn :: IO Integer
   if n == 0
      then return ()
      else do
         let maxVal = 1000000
         let p = findTerm 3 maxVal n
         let q = findTerm (p+2) maxVal n
         let r = div n (p * q)
         putStrLn (show n ++ " = " ++ show p ++ " x " ++ show q ++ " x " ++ show r)
         main

findTerm i j n
   | mod n i == 0 = i
   | otherwise = findTerm (i+2) j n

Por hoje era isso! Espero que tenham curtido mais esse post.

Chave PIX do Blog: 6d8bc7a8-5d74-493a-ab7a-3515baf35956.

Toda doação é bem-vinda Obrigado e até a próxima!