20 Janeiro 2017      13:56

Está aqui

OS PRIMOS SABEM GUARDAR SEGREDO

Durante séculos o estudo dos números primos consistia num mero exercício de curiosidade matemática, impelido pelo fascínio que as estranhas propriedades destes números exerciam sobre os seus estudiosos. Esta faceta do interesse pelos números primos foi já alvo da nossa atenção, no artigo de Abril de 2014 intitulado “Primos que valem 1 milhão de dólares” onde se elencavam alguns episódios da história dos números primos e se abordavam as propriedades destes números.

Actualmente o fascínio pelos números primos mantém-se, e a busca de novos números primos continua com a ajuda de potentes computadores e de novos algoritmos, mas a importância destes números atingiu uma fasquia inimaginável por aqueles que, em diferentes momentos da história da Matemática, se dedicaram ao seu estudo. Os números primos são, hoje em dia, de importância fulcral para a codificação de mensagens, assegurando, por exemplo, a segurança das transacções bancárias via internet.

Desde tempos remotos que o Homem sente a necessidade de assegurar comunicações seguras, tendo desenvolvido a arte de cifrar e decifrar mensagens. A criptografia é a área do conhecimento que tem como objectivo codificar a informação de forma a propiciar a sua transmissão segura entre um transmissor e um receptor. Para isso, são necessárias uma chave e um algoritmo, que consiste numa regra para transformar o texto original no texto encriptado. A acção inversa de procurar uma forma de decifrar uma mensagem encriptada, sem o conhecimento da chave, chama-se criptoanálise.

De acordo com as ferramentas de cada época, foram surgindo diversas técnicas de encriptação das quais podemos destacar, uma das mais antigas de que existe conhecimento, o código de substituição simples de César. Esta técnica, como outras, tem como característica marcante a sua simetria, ou seja, o facto de a chave utilizada para cifrar uma mensagem ser a mesma que é usada para a decifrar.

Nos anos 70 do século XX, a criptografia de chaves simétricas deu lugar à criptografia de chaves assimétricas, que se baseia na teoria dos números. Em 1977, Ron Rivest, Leonard Adleman e Adi Shamir criaram o sistema RSA (“R” de Rivest, “S” de Shamir e “A” de Adleman), um dos algoritmos de encriptação mais seguros, que se baseia na dificuldade de encontrar os factores primos de um determinado número, resultante do produto de dois números primos.

Apesar da sua simplicidade (relembremos que um número primo é um número inteiro, maior que 1, que possui apenas dois divisores, ele próprio e o 1), os números primos têm a extraordinária capacidade de gerar todos os demais números inteiros, uma vez que, tal como afirma o teorema fundamental da aritmética, qualquer número inteiro, maior que 1, pode ser escrito como um produto de números primos. Sendo a ordem dos factores irrelevante, essa representação é única.

Multiplicar dois números primos é uma tarefa rápida mas se, dispondo apenas do resultado, quisermos encontrar os números primos (factores) que deram origem a esse resultado, o processo é bem mais demorado.

A busca dos números primos que originam determinado número inteiro, ou seja, a transformação de um qualquer número num produto de números primos, é um processo muito simples e familiar a muitos que o conheceram, nos tempos de escola, com a designação de “factorização em números primos” ou “decomposição em factores primos”. Esse processo consiste na divisão do número inteiro (e consequentes quocientes das divisões seguintes) pelos números primos que originem divisões inteiras até que se obtenha uma representação que só contenha números primos. Como exemplo, vejamos como se processa a decomposição do número 36 em factores primos.

Percorrendo a lista dos números primos: 2, 3, 5, 7, 11, 13 … , comecemos por verificar se 36 é divisível por 2. De facto, 36 é divisível por 2, obtendo-se como quociente (resultado) dessa divisão o número 18.

36 | 2

18 |

Isto significa que 36 pode ser escrito como o produto de dois factores, o 2 e o 18,

36 = 2 x 18

NOTA: Caso não fosse divisível por 2, tentaríamos o próximo número primo, o 3. Se não fosse divisível por 3 passaríamos ao número primo seguinte, e assim sucessivamente.

Com esta primeira divisão não atingimos o objectivo, pois pretendemos que o produto seja apenas constituído por factores primos … e o quociente desta divisão, o 18, não é primo.

Vamos prosseguir com as divisões, dividindo 18 pelo primeiro número primo que o divide. Verificamos que 18 é divisível por 2, sendo o quociente desta divisão igual a 9.

36 | 2

18 | 2

  9 |

Isto significa que 18 pode ser escrito como o produto de dois factores, o 2 e o 9, portanto 36 = 2 x 2 x 9

Com o produto 2 x 2 x 9 não atingimos ainda o objectivo, pois pretendemos que o produto seja apenas constituído por factores primos e 9 não é primo. Vamos, então, prosseguir com as divisões.

O número 9 não é divisível pelo primeiro número primo (2), mas é divisível por 3.

36 | 2

18 | 2

  9 | 3

  3 |

Sendo 9 = 3 x 3, podemos escrever 36 = 2 x 2 x 3 x 3

Como o quociente desta última divisão é um número primo (o 3) já não faremos mais divisões pois conseguimos atingir o objectivo de escrever o 36 como um produto de números primos

2 x 2 x 3 x 3

Escolhendo números primos suficientemente (muito) grandes, o tempo gasto para factorizar o resultado do seu produto será, mesmo para o mais potente dos computadores, de tal forma elevado que tal se revela impraticável. Só para ter uma ideia de como o processo de factorização se torna mais moroso, quando os factores primos são maiores, experimente factorizar um número ligeiramente superior ao que usámos antes. Experimente, por exemplo, 611. Chegará à conclusão que a busca do primeiro factor primo se revelou agora mais demorada, uma vez que 611 não é divisível nem por 2, nem por 3, nem por 5, nem por 7, nem por 11, sendo 13 o seu primeiro factor primo, e 47 o outro factor primo (concluindo-se que 611= 13 x 47).

Enquanto não houver um algoritmo que permita a factorização do produto de dois números primos muito grandes em tempo útil, a escolha de dois números primos grandes, de entre as largas dezenas de milhões de números primos já conhecidos, é o suficiente, por enquanto, para garantir a segurança das transacções bancárias via internet e de outras operações que recorrem à encriptação pelo sistema RSA.

Imagem de capa de tri-angulo.pt