A criptografia moderna não existiria sem os números primos - 29/09/2017 - Marcelo Viana - Colunistas - Folha de S.Paulo
Wednesday, 18-Jul-2018 12:56:33 BRT
A criptografia moderna não existiria sem os números primos
Criptografia ajuda na prote��o de dados pessoais
Em 1770, o matem�tico ingl�s Edward Waring (1736-1798) escreveu o livro "Meditationes Algebricae" ("Medita��es sobre a �lgebra"), onde se l� a seguinte afirma��o: "Se p � um n�mero primo, a quantidade 1 x 2 x 3 x... x (p-1) + 1 dividida por p d� um n�mero inteiro. Esta elegante propriedade dos n�meros primos foi descoberta pelo eminente John Wilson, um homem muito versado em assuntos matem�ticos".
Esta homenagem entusiasmada n�o � para ser tomada a s�rio: al�m de ser amigo e ex-aluno, Wilson apoiara a controversa escolha de Waring como sucessor de Isaac Newton na Universidade de Cambridge. Havia um favor pol�tico a pagar...
Essa propriedade dos primos j� havia sido mencionada pelo matem�tico e fil�sofo mu�ulmano Ibn al-Haytham, que viveu no Egito em torno do ano 1000. Outro que fizera a descoberta antes de Wilson foi Gottfried Wilhelm Leibniz (1646-1716), embora n�o a tivesse publicado. Mas nenhum deles provou a sua veracidade, eles apenas verificaram alguns casos.
Waring tentou justificar: "Teoremas deste g�nero ser�o muito dif�ceis de provar por causa da falta de uma nota��o para representar n�meros primos". Ao ler isso, o grande Carl Friedrich Gauss (1777-1855) exclamou depreciativamente "Notationes versus notiones!", querendo dizer que em matem�tica as no��es s�o muito mais importantes que as nota��es.
Ali�s, o teorema foi demonstrado logo em 1771, por Joseph-Louis Lagrange (1736-1813), o qual tamb�m provou a rec�proca: se p n�o � primo, ent�o o quociente de 1 x 2 x 3 x... x (p-1) + 1 por p n�o � um n�mero inteiro. Talvez devesse ser chamado teorema de Lagrange. Mas ficou "teorema de Wilson" mesmo.
A defini��o � simples, todo mundo aprende na escola: um n�mero inteiro maior que 1 � primo se ele n�o pode ser escrito como produto de dois n�meros inteiros maiores que 1. Mas a teoria dos primos � rica e sofisticada. Euclides mostrou por volta de 300 a.C. que existe uma quantidade infinita de primos. Atualmente, o maior conhecido � 2^74.207.281 − 1, que tem 22.338.618 d�gitos.
Euclides tamb�m provou o teorema fundamental da aritm�tica: "todo inteiro maior que 1 pode ser escrito como produto de primos e essa escrita � �nica, a menos da ordem dos fatores". Assim, os primos s�o as pe�as b�sicas com que s�o constru�dos todos os n�meros inteiros. A prop�sito, � por isso que eles s�o chamados desse jeito: "primus" � "primeiro", em latim.
Dois � o �nico primo par e no come�o todos os �mpares s�o primos: 3, 5, 7. Mas a partir do 9 = 3 x 3 come�am a aparecer lacunas –por exemplo, de 114 a 126 n�o h� um �nico primo– e fica muito dif�cil prever quando surgir� o pr�ximo.
O teorema dos n�meros primos, provado pelo franc�s Jacques Hadamard (1865-1963) e pelo belga Charles-Jean de la Vall�e Poussin (1866-1962), afirma que "a fra��o dos n�meros menores que um dado N que s�o primos � aproximadamente 1/log N", onde log N representa o logaritmo natural. Portanto, a percentagem de primos entre 1 e N vai diminuindo � medida que N cresce.
O alem�o Don Zagier, especialista em teoria dos n�meros, escreveu uma vez que "os primos surgem como ervas daninhas entre os n�meros inteiros, parecendo n�o obedecer a nenhuma regra a n�o ser a do acaso, mas tamb�m apresentam uma regularidade impressionante e h� leis governando o seu comportamento, �s quais eles obedecem com precis�o quase militar".
Os matem�ticos Ben Green, brit�nico, e Terence Tao, australiano, conseguiram avan�ar muito no estudo do comportamento "aleat�rio" dos primos, o que lhes permitiu provar em 2004 que existem progress�es aritm�ticas m + r, m + 2r, m + 3r,..., m + kr de primos com "comprimento" k t�o grande quanto se queira. Esse resultado espetacular valeu a Tao a Medalha Fields, pr�mio mais prestigioso da matem�tica, em 2006. A progress�o aritm�tica de primos mais longa que se conhece atualmente tem comprimento 26.
Em geral, pode ser muito dif�cil verificar se um dado n�mero � primo ou n�o: claro que sempre podemos tentar dividir por todos os n�meros menores que ele, mas isso demora muito se o n�mero for grande. O melhor m�todo conhecido foi descoberto em 2002 pelos indianos Manindra Agrawal, Neeraj Kayal e Nitin Saxena, mas mesmo ele � pouco eficaz para ser usado na pr�tica.
Ainda mais dif�cil �, dado um inteiro qualquer, encontrar a sua fatoriza��o em n�meros primos dada pelo teorema fundamental da aritm�tica. Essa dificuldade tem um lado muito positivo: est� na origem da principal aplica��o pr�tica dos n�meros primos, a criptografia moderna.
N�s matem�ticos estamos habituados a que nos perguntem para que serve o que fazemos, e nem sempre � f�cil responder. Fico imaginando um matem�tico do Egito antigo pedindo financiamento para sua pesquisa sobre primos.
"Mas isso � matem�tica pura, para que serve?", questiona o fara�. "� muito bonito, majestade", responde o colega, "e tamb�m vai ser muito importante quando inventarem a tecnologia da informa��o, daqui a 4.000 anos".
Ser� que conseguiria o dinheiro?
Para terminar, proponho um debate pol�mico. O n�mero 1 costumava ser considerado primo, mas no s�culo 20 foi exclu�do da lista.
O que pensam os leitores? O 1 deveria ser classificado como primo ou n�o? Por qu�? Respostas s�o bem-vindas pelo e-mail vianafolhasp@gmail.com.