{"id":72039,"date":"2017-02-14T18:56:45","date_gmt":"2017-02-14T20:56:45","guid":{"rendered":"http:\/\/clubes.obmep.org.br\/blog\/?page_id=72039"},"modified":"2024-11-26T22:56:45","modified_gmt":"2024-11-27T01:56:45","slug":"fatorando-de-um-jeito-diferente","status":"publish","type":"page","link":"https:\/\/clubes.obmep.org.br\/blog\/fatorando-de-um-jeito-diferente\/","title":{"rendered":".Sala de Estudo: Fatorando de um jeito diferente (N\u00edvel avan\u00e7ado)"},"content":{"rendered":"
\n\n\n
\"\"<\/td>\n\n

Se voc\u00ea n\u00e3o se lembra ou n\u00e3o estudou o Teorema da Fatora\u00e7\u00e3o \u00danica, clique AQUI<\/strong><\/span><\/a>!<\/span><\/p>\n<\/td>\n<\/tr>\n<\/table>\n<\/div>\n

\n

\n
Fatorando de um jeito diferente<\/strong><\/div>\n
\n
\n

\n

<\/span>O m\u00e9todo de fatora\u00e7\u00e3o que estudamos usualmente pode tornar-se invi\u00e1vel para n\u00fameros muito grandes, mesmo que utilizemos um computador potente. De fato, ainda n\u00e3o se conhece um algoritmo por meio do qual um computador possa fatorar n\u00fameros imensos em tempo h\u00e1bil.
\n<\/span>S\u00f3 para voc\u00eas terem uma ideia, consideremos um n\u00famero primo [tex]p[\/tex] de [tex]47[\/tex] algarismos. Assim, [tex]p \\gt 10^{46}[\/tex] e, portanto, [tex]\\sqrt{p}\\gt 10^{23}[\/tex]. Pelo algoritmo tradicional de fatora\u00e7\u00e3o, aquele por tentativas, precisar\u00edamos testar a divisibilidade de [tex]p[\/tex] por todos os primos menores ou iguais \u00e0 sua raiz quadrada. H\u00e1 quase [tex]2\\times 10^{21}[\/tex] primos menores que [tex]10^{23}[\/tex]. (Se voc\u00ea se interessou por essa informa\u00e7\u00e3o, clique AQUI<\/strong><\/span><\/a>.)<\/span> Para transformarmos essa informa\u00e7\u00e3o em tempo de c\u00e1lculo, precisamos ter uma ideia de quantas divis\u00f5es um computador \u00e9 capaz de efetuar em um segundo. Vejam s\u00f3: <\/p>\n

<\/span>O supercomputador <\/strong><\/span><\/a>inaugurado pela USP em julho de 2015 faz algo em torno de [tex]4,6\\times 10^{13}[\/tex] opera\u00e7\u00f5es por segundo. Se utiliz\u00e1ssemos esse supercomputador para fazer as divis\u00f5es, precisar\u00edamos de aproximadamente [tex]\\dfrac{2\\times 10^{21}}{4,6\\times 10^{13}}\\approx 4,348\\times10^{7}[\/tex] segundos, o que equivale a mais de [tex]1[\/tex] ano e [tex]4[\/tex] meses. <\/p>\n\n\n
\"\"<\/td>\n\n

Se voc\u00ea achou que um ano e quatro meses \u00e9 um tempo razo\u00e1vel para que sejam efetuadas [tex]2\\times 10^{21}[\/tex] divis\u00f5es, tente calcular o tempo de se fazer, por exemplo, [tex]10^{40}[\/tex] divis\u00f5es . . .<\/p>\n

 <\/td>\n<\/tr>\n<\/table>\n

<\/span>Como fatorar n\u00fameros \u00e9 uma quest\u00e3o central de seguran\u00e7a em alguns m\u00e9todos de criptografia, al\u00e9m de ser, \u00e9 claro, um problema fascinante, matem\u00e1ticos de v\u00e1rias \u00e9pocas t\u00eam se debru\u00e7ado nesta quest\u00e3o e oferecido ao mundo novos m\u00e9todos de fatora\u00e7\u00e3o, mais poderosos e, obviamente, menos naturais e menos conhecidos. Nesta Sala, apresentaremos um m\u00e9todo que poderia ser classificado como pouco conhecido: a Fatora\u00e7\u00e3o por Fermat<\/strong>.<\/p>\n

Vamos l\u00e1?<\/p>\n

\n

\n
\n
\n

\n

Fatora\u00e7\u00e3o por Fermat<\/p>\n

\n

<\/span>Como dissemos na apresenta\u00e7\u00e3o da Sala, o m\u00e9todo comum de fatora\u00e7\u00e3o pode tornar-se invi\u00e1vel para n\u00fameros cujo menor fator primo \u00e9 muito grande, mesmo utilizando um computador potente. Entretanto, o matem\u00e1tico franc\u00eas Pierre de Fermat<\/em><\/strong><\/span><\/a> (1601-1665) desenvolveu um m\u00e9todo muito eficaz para a fatora\u00e7\u00e3o de n\u00fameros que possuem um fator pr\u00f3ximo \u00e0 sua raiz quadrada. Este m\u00e9todo ficou conhecido por Fatora\u00e7\u00e3o por Fermat<\/strong>.
\n<\/span>Mesmo n\u00e3o sendo t\u00e3o natural quanto o m\u00e9todo de fatora\u00e7\u00e3o que j\u00e1 conhecemos, a Fatora\u00e7\u00e3o por Fermat n\u00e3o \u00e9 um m\u00e9todo dif\u00edcil de ser compreendido, al\u00e9m de ser bastante interessante. Ele \u00e9 a base para muitos dos poderosos m\u00e9todos de fatora\u00e7\u00e3o que existem. Muito provavelmente, Fermat explicitou este m\u00e9todo pela primeira vez em 1643, em uma carta endere\u00e7ada ao matem\u00e1tico Marin Mersenne<\/em>. Na suposta carta, Fermat teria fatorado o n\u00famero [tex]2.027.651.281[\/tex] utilizando esse m\u00e9todo (Ver refer\u00eancia [4], p. 5)<\/span>.
\n<\/span>Vejamos do que se trata.<\/p>\n

\n

\n

O m\u00e9todo<\/p>\n

\n

\n

Seja [tex]n[\/tex] o inteiro maior do que [tex]1[\/tex] que queremos fatorar. <\/p>\n

O objetivo do m\u00e9todo que vamos apresentar \u00e9 encontrar inteiros n\u00e3o negativos [tex]x[\/tex] e [tex]y[\/tex], [tex]x \\gt y[\/tex], tais que [tex]n=x^2-y^2.[\/tex]<\/p>\n

Mas por que isso nos ajudaria? <\/p>\n

Sabemos que [tex]x^2-y^2=(x-y)(x+y)[\/tex]; assim, se conseguirmos encontrar inteiros n\u00e3o negativos [tex]x[\/tex] e [tex]y[\/tex], com [tex]x>y[\/tex], tais que [tex]n=x^2-y^2[\/tex], ent\u00e3o ter\u00edamos uma fatora\u00e7\u00e3o de [tex]n[\/tex], n\u00e3o \u00e9? N\u00e3o necessariamente em fatores primos; mas, se nenhum dos fatores [tex](x-y)[\/tex] e [tex](x+y)[\/tex] for [tex]1[\/tex], ter\u00edamos a garantia de que [tex]n[\/tex] \u00e9 composto (obtemos uma decomposi\u00e7\u00e3o de [tex]n[\/tex] diferente de [tex]n=1\\cdot n[\/tex]), al\u00e9m de termos obtido uma ajuda na decomposi\u00e7\u00e3o de [tex]n[\/tex] em fatores primos. Assim,<\/p>\n

demos um passo na dire\u00e7\u00e3o certa! <\/p>\n

Antes de estabelecermos como determinar efetivamente os inteiros n\u00e3o negativos [tex]x[\/tex] e [tex]y[\/tex], vamos fazer algumas observa\u00e7\u00f5es.<\/p>\n