É fácil provar que um número é primo?
|
Qui 30 Jun 2005 04:45 |
- Detalhes
- Categoria: Matemática Numaboa
- Atualização: Segunda, 22 Fevereiro 2010 13:30
- Autor: vovó Vicki
- Acessos: 36447
Os números primos, devido ao seu comportamento exótico, há milênios são um desafio para as mentes mais privilegiadas e não foi por acaso que se transformaram nas estrelas da criptologia moderna. Possuem uma característica marcante: até este momento da História, não existe um único método capaz de criar um número primo!
Apesar de existitem infinitos números primos, eles precisam ser descobertos, literalmente garimpados entre os também infinitos números compostos. Números compostos são todos aqueles produtos da multiplicação de números primos. A esta altura você pode perguntar: e daí? É que na criptologia existe a preocupação de se esconder a chave dos segredos e, se a chave for um número primo, é possível escondê-lo muito bem multiplicando-o por outro número primo.
O porque disto fica claro com um exemplo simples. Se a chave for 2 (um número primo), posso tentar escondê-la multiplicando-a por 3 (outro número primo). Acontece que é muito fácil fazer esta conta de cabeça: 6 é o resultado de 2 x 3. Agora, tente encontrar o número primo escondido em 5353. Vai demorar um bom tempo para descobrir que é o resultado de 53 x 101. E estes são primos muito, mas muito pequenos!
Agora, imagine a multiplicação de dois números primos gigantes. Até mesmo o computador, com um excelente programa para fatorar números compostos, vai demorar um tempão para encontrar os primos escondidos 
Mas quanto é este tempão? Depende do tamanho e da complexidade do problema. Neste caso específico o fato é que, independentemente do tempo que levar, é preciso decidir se determinado número é primo ou não.
PROBLEMAS DE DECISÃO
Existe uma brincadeira bastante conhecida na qual um dos participantes escolhe uma palavra que os outros precisam descobrir fazendo perguntas. A restrição é que o "dono" da palavra só pode responder com sim ou não. Por exemplo, se a palavra escolhida for banana e a pergunta for "é um animal?", a resposta é obviamente "não" e, se a pergunta for "é uma fruta?", a resposta é "sim". Este tipo de pergunta é conhecida como questão sim-ou-não e o problema apresentado é um problema de decisão típico. Quando a pergunta final "é uma banana?" for respondida com "sim", o problema está resolvido.
Todas as perguntas que podem ser feitas para este problema de decisão fazem parte de uma classe especial porque geram apenas respostas de dois tipos: verdadeiro/falso ou sim/não. Em lógica, este tipo de resposta é conhecido como resposta de valor Booleano. Toda vez que houver uma classe de perguntas que possam ser respondidas com valores Booleanos, o problema de decisão ao qual elas pertencem pode ser resolvido. O tempo que se leva para resolver o problema são outros quinhentos: depende das perguntas formuladas. Quanto mais calibradas forem as perguntas, menos delas serão necessárias e menor será o tempo gasto com o problema. A elaboração destas perguntas é conhecida como procedimento de decisão ou algoritmo.
Transformando um Problema de Decisão num Problema Computacional
Como tudo o que é Booleano é binário (baseado em apenas dois valores) e tudo o que é binário pode ser facilmente processado por um computador, a máquina ideal para ajudar a resolver problemas de decisão é o próprio. Basta transformar o problema de decisão num problema computacional. Para fazer esta transformação podemos reduzir a classe das perguntas num predicado e depois reduzir este predicado numa função. Como?
Se considerarmos o conjunto das perguntas como P e cada uma delas como x1, x2, ..., xn, o predicado pode ser expresso por P(x1, x2, ..., xn) e contém todas as infinitas perguntas possíveis. Para responder cada uma das perguntas com sim ou não precisamos de uma ferramenta de cálculo. Esta ferramenta recebe informação e devolve um resultado de acordo com a informação recebida. Este tipo de ferramenta é conhecido como função. A função para o predicado que foi criado é a seguinte: f(x1, x2, ..., xn). A decisão se P(x1, x2, ..., xn) é verdadeiro ou falso equivale ao cálculo do valor de f(x1, x2, ..., xn). Em matematiquês, a função funciona da seguinte maneira:
f(x1) = 1 se P(x1) for verdadeiro
f(x1) = 0 se P(x1) for falso
... e, generalizando
f(x1,...,xn) = 1 se P(x1,...,xn) for verdadeiro
f(x1,...,xn) = 0 se P(x1,...,xn) for verdadeiro
O TAMANHO DO PROBLEMA
Para muitos problemas, o tamanho é definido de acordo com o número de bits necessários para representar a entrada de dados (input da função). Por exemplo, se o problema for elevar ao quadrado determinado número inteiro, o tamanho do problema é a quantidade de bits necessários para representar este inteiro. Digamos que se queira calcular o quadrado de números de 0 até 5. A notação binária destes inteiros é:
Decimal Binário
=====================
0 0
1 1
2 10
3 11
4 100
5 101
Neste caso, o tamanho do problema é igual a 3, os bits necessários para dar entrada nos inteiros 4 e 5. Para calcular a quantidade de bits necessários para representar qualquer número inteiro basta calcular o logaritmo na base 2 deste inteiro.
A TEORIA DA COMPLEXIDADE COMPUTACIONAL
A Teoria da Complexidade Computacional faz parte da Teoria da Computação e trata dos recursos necessários para resolver determinado problema. Quanto maiores forem as necessidades, maior será a complexidade do processo computacional. Os recursos mais comuns são o tempo e o espaço. Quando a solução do problema requer comunicação, a largura de banda também é um recurso que precisa ser analisado.
O tempo NÃO é o tempo do relógio ou os ciclos do processador, mas a quantidade de passos necessários para resolver o problema. O tempo do relógio pode indicar a eficiência de um processo mas, quando se trata de complexidade, o tempo indica se o caminho a ser seguido requer um, dois, ou um zilhão de passos, não importando quanto demora para realizá-los. O espaço se refere à quantidade de memória necessária para que o problema possa ser resolvido.
Classes P de Complexidade
Na Teoria da Complexidade Computacional, a classe P é constituída por todos os problemas de decisão que podem ser resolvidos numa máquina sequencial determinística num espaço de tempo que seja polinomial de acordo com o tamanho da entrada. :confused: Creeeeedo! Que papo é este? Sequencial determinística e tempo polinomial? Vamos por partes...
Uma máquina sequencial é aquela que realiza tarefas passo a passo, um após o outro, em sequência. Quando cada uma das instruções (passos) segue um caminho determinado, sem atalhos ou ramificações, diz-se que a máquina é determinística. Quando as instruções se ramificam, abrindo vários caminhos que podem ser seguidos, a máquina é do tipo não-determinístico. Resumindo: a máquina determinística segue um trajeto único de instruções e a máquina não-determinística pode ramificar o trajeto.
Agora é a vez do tempo polinomial, lembrando mais uma vez que este tempo representa o número de passos necessários para resolver determinado problema. É o tempo de computação de um problema onde o tempo, T(n), não seja maior do que uma função polinomial do tamanho do problema, n. Costuma-se usar a notação Big O para expressar este tempo.
Big O
Um exemplo vai deixar a coisa mais clara. Digamos que, ao analisar determinado problema da classe P de tamanho n, os cientistas da computação determinaram o tempo T(n) = 4n2 - 2n + 2. Digamos que o tamanho do problema seja 2. Neste caso, T(2) = 4 x 22 - 2 x 2 + 2, o que dá o tempo T(n) = 14. A porção - 2n + 2 do polinômio pesou no resultado pois, sem ela, o resultado seria 16 (a diferença de 14 para 16 é de cerca de 14%). À medida que o valor de n for aumentando, esta porção do polinômio vai influindo cada vez menos no resultado e n2 vai se tornando cada vez mais dominante. Por exemplo, se n for igual a 10, então T(10) = 4 x 102 - 2 x 10 + 2 = 382. Novamente, se a porção - 2n + 2 for ignorada, o resultado é 400 e a diferença de 382 para 400 é de pouco menos de 5%. Até o coeficiente 4 do termo 4n2 vai perdendo o fôlego se n for um valor muito grande. É aí que entra a notação Big O. Esta notação serve para mostrar o que acontece com as mais diversas funções quando n tende ao infinito.
A função polinomial T(n) = 4n2 - 2n + 2 pode ser expressa em Big O como O(n2). Isto é o mesmo que dizer que T(n) pertence a O(n2) ou, em notação matemática, T(n)
O(n2), que é um tempo polinomial porque sua origem foi um polinômio.
A seguir estão alguns tempos em notação Big O ordenados dos de crescimento mais lento para os de crescimento mais rápido:
O(1) ............ constante
O(log n) ........ logarítmico
O(n) ............ linear
O(n2)............ quadrático
O(nc), c > 1 .... polinomial
O(n!) ........... fatorial
O porque do interesse pela classe P
A classe P é interessante porque a maioria dos problemas que estão em P podem ser solucionados eficientemente na vida real. Existem exceções por conta de constantes muito grandes na função polinomial, mas, em geral, podemos considerar que a maioria dos problemas da classe P podem ser resolvidos. E agora, finalmente, o que tudo isto tem a ver com os números primos 
OS PRIMOS ESTÃO EM P
Em 2002, o Prof. Manindra Agrawal e dois de seus alunos, Nitin Saxena e Neeraj Kayal, descobriram um algoritmo determinístico de tempo polinomial (agora você já sabe o que é isto )para testar se um número é primo ou não. O que esta notícia tem de tão especial? É que muitas cabeças pensantes, durante vários séculos, procuraram por um teste de primalidade de tempo polinomial. Este teste somente em 2002 se tornou realidade e foi batizado de AKS2002 em homenagem aos seus autores. Foi notícia nos principais veículos de comunicação do mundo todo.
Agrawal, Kayal e Saxena deram um show de Teoria da Complexidade e provaram que a primalidade é um problema da classe P, portanto um problema que pode ser transformado num problema computacional que, por sua vez, pode ser resolvido num tempo polinomial relativo ao número de bits necessários para expressar o número que está sendo testado.
Agora, de posse de todas estas informações, a resposta para o título deste texto pode ser dada sem pestanejar: SIM, É FÁCIL PROVAR COM ABSOLUTA CERTEZA QUE UM NÚMERO É PRIMO!
Onde encontrar o algoritmo AKS2002
- Uma descrição do algoritmo e uma explicação simplificada de como funciona está em Prime Pages.
- O texto original está na página dos autores.
- Descrições, Aperfeiçoamentos, Implementações e muito mais estão na FatPhil's Home Page.
UMA PERGUNTA MUITO IMPORTANTE
Este algoritmo vai permitir quebrar outros algoritmos criptogáficos?
A resposta é NÃO. Não podemos confundir testes de primalidade com fatoração.
Antes do AKS2002 já existiam outros testes de primalidade. Todos servem apenas para afirmar se determinado número é primo ou composto. A diferença estre o AKS e os anteriores é que, com o AKS é possível afirmar com certeza que determinado número é primo. Com os anteriores sempre havia uma pequena probabilidade (na verdade, mínima) de que o resultado não fosse correto.
A fatoração não é um teste de primalidade. Ela serve para individualizar todos os números primos cuja multipicação resulta no inteiro pesquisado. Se houvesse uma algoritmo eficiente para fatorar números muito grandes, compostos por primos também muito grandes, este seria um perigo para certos algortimos criptográficos baseados exatamente na dificuldade de realizar esta operação. Exemplos destes algoritmos são o RSA e esquemas de assinaturas.
vovó Vicki