Um dos fundamentos da criptografia e dos sistemas de assinatura digital são os números primos. O princípio que rege a criptografia assimétrica (RSA) é o fato de ser rápido descobrir se um número é primo e é lento fatorar um número.
O RSA fica para outro post, agora queria focar na pergunta: como faz para saber se um número é primo?
int isPrimo (int x) {
if (x < 4) return 1;
for (int i=0; i < x; i++) {
if (x%i == 0) return 0;
}
return 1;
} |
int isPrimo (int x) {
if (x < 4) return 1;
for (int i=0; i < x; i++) {
if (x%i == 0) return 0;
}
return 1;
}
Obviamente esta função não é a melhor, ela roda em O(n) ou seja o tempo de execução cresce linearmente com o tamanho do número em questão.
Uma otimização que alguns alunos espertos no curso de Computação I fazem é a seguinte:
int isPrimo (int x) {
if (x < 4) return 1;
for (int i=0; i =< x/2; i++) {
if (x%i == 0) return 0;
}
return 1;
} |
int isPrimo (int x) {
if (x < 4) return 1;
for (int i=0; i =< x/2; i++) {
if (x%i == 0) return 0;
}
return 1;
}
Isto diminui o tempo de execução pela metade mas não muda a complexidade do algoritmo, ela continua sendo O(n). Portanto para números grandes isto não ajuda muito.
Uma coisa que podemos usar para melhorar a complexidade (ainda não ajuda muito, mas hoje paramos por aqui) é o fato de que se um número não tem nenhum divisor menor que a raiz quadrada dele ele não tem nenhum divisor (a prova disto é fácil e fica como exercício para o leitor 🙂 )
int isPrimo (int x) {
if (x < 4) return 1;
for (int i=0; i =< sqrt(x); i++) {
if (x%i == 0) return 0;
}
return 1;
} |
int isPrimo (int x) {
if (x < 4) return 1;
for (int i=0; i =< sqrt(x); i++) {
if (x%i == 0) return 0;
}
return 1;
}
Neste caso a complexidade que era O(n) passa a ser O(√n)
Melhorou? Sim. Mas ainda não é o suficiente. No próximo capítulo desta série, veremos métodos que dizem se um número é provavelmente primo.
Se você achar algum erro nos códigos acima, comente.
