Fatoração em primos

O resultado mais importante sobre os números primos é o chamado Teorema Fundamental da Aritmética que garante que todo número maior que 1 pode ser decomposto em fatores primos. Vamos apresentar o algoritmo que executa mais operações, mas que é mais fácil de ser entendido. O algoritmo consiste em testar os números menores ou iguais   e ir dividindo a medida do possível:

#include <stdio.h>
#include <math.h>
#include <vector>
#include <iostream>
#include <stdlib.h>
using namespace std;

vector <int> fatora(int n){
  int i,limite;
  vector <int> primos;
  i=2;
  limite = (int)sqrt(n);
  while(n > 1 && i<=limite){
    //se i divide n entao i eh primo retira todos os fatores i de n
    while(n%i==0){
      primos.push_back(i);
      n=n/i;
    }
    i=i+1;
  }
  //se i >= raiz de n entao n eh primo
  if(n>1)
    primos.push_back(n);
  return primos;
}

int main(){
  vector <int> primos;
  primos = fatora(120);
  printf("%d",primos[0]);
  for(int i=0;i<primos.size();i++)
    printf("*%d",primos[i]);
  printf("\n");
  system("PAUSE");
} 

SAÍDA 

2*2*2*2*3*5
Pressione qualquer tecla para continuar. . .

Podemos provar que nenhum número composto será adicionado no vetor primos.

Teorema: O algoritmo fatora encontra a decomposição em fatores primos.

Prova: Suponha por absurdo que um número não-primo foi adicionado no vetor primos (vetor que guarda a decomposição em fatores primos). Seja d o menor número não-primo adicionado no vetor primos. Pelo Teorema Fundamental da Aritmética, d também pode ser decomposto em fatores primos. Considere a seguinte decomposição de d = p_1*p_2*..._*p_k onde p_i < d. Logo, existe um primo p_i que foi “pulado” durante o algoritmo uma vez que p_i < d. Absurdo, todos os números menores que d são testados antes de d.  

O pior caso desse algoritmo tem a seguinte complexidade:

A segurança do sistema RSA depende da dificuldade da fatoração de um número n em fatores primos. Vamos imaginar que queiramos quebrar a criptografia de um sistema RSA com uma chave de 1024 bits. Logo, n ~ 2¹⁰²⁴ ~ 2¹⁰⁰⁰~ (2¹⁰)¹⁰⁰ ~ (10³)¹⁰⁰~ 10³⁰⁰. Precisamos testar aproximadamente ~10¹⁵⁰ números. Considerando que seja possível testar 10⁹ fatores por segundo. Para testar todos os valores possíveis ~10¹⁴¹ segundos ~ 10¹³⁰ milênios.  
 

Programa em JavaScript que descobre a decomposição em fatores primos utilizando esse algoritmo