{"id":1486,"date":"2021-12-12T08:25:21","date_gmt":"2021-12-12T11:25:21","guid":{"rendered":"http:\/\/localhost\/?page_id=1486"},"modified":"2023-01-06T14:48:42","modified_gmt":"2023-01-06T17:48:42","slug":"testes-de-primalidade","status":"publish","type":"page","link":"http:\/\/localhost\/index.php\/ensino\/fundamentos-de-algebra\/testes-de-primalidade\/","title":{"rendered":"Teste de primalidade de Fermat"},"content":{"rendered":"
\nPara um primo $p$, o Pequeno Teorema de Fermat afirma que
\n\\begin{align*}
\na^p&\\equiv a\\pmod p\\quad\\mbox{para todo}\\quad a\\in \\Z;\\\\
\na^{p-1}&\\equiv 1\\pmod p\\quad\\mbox{para todo}\\quad a\\in \\Z\\mbox{ tal que }p\\nmid a.
\n\\end{align*}<\/p>\n

O Pequeno Teorema de Fermat pode ser usado para dar um crit\u00e9rio suficiente para decidir se um n\u00famero \u00e9 composto.<\/p>\n

Assuma que $n\\geq 2$ \u00e9 um n\u00famero natural. Se $b^{n-1}\\not\\equiv 1\\pmod n$ para algum $b\\in\\{2,\\ldots,n-2\\}$, ent\u00e3o $n$ \u00e9 um n\u00famero composto.<\/div>\n

Observe que a congru\u00eancia $b^{n-1}\\equiv 1\\pmod n$ pode ser checada para $n$ muito grande usando o Algoritmo da Exponencia\u00e7\u00e3o R\u00e1pida.<\/p>\n

Seja
\n\\[
\nn=100000000000000000039000000005700000000000000002223.
\n\\]
\nQueremos saber se $n$ \u00e9 um n\u00famero primo ou ele \u00e9 composto. Usando nossa implementa\u00e7\u00e3o do algoritmo para calcular $2^{n-1}\\pmod n$, obtemos que
\n\\[
\n2^{n-1}\\equiv 496813\\ldots 506416 \\neq 1\\pmod n.
\n\\]
\nPortanto $n$ \u00e9 um n\u00famero composto. \u00c9 muito mais dif\u00edcil verificar que de fato
\n\\[
\nn=100000000000000000039\\cdot 10000000400000000000000000000057.
\n\\]<\/div>\n
\nSe $n\\geq 2$ e $b^{n-1}\\equiv 1\\pmod n$ com algum $b\\in\\{2,\\ldots,n-1\\}$, ent\u00e3o o n\u00famero $n$ chama-se pseudoprimo<\/em> para a base $b$.<\/div>\n
\nMostre para $2\\leq b<n$ que se $n$ \u00e9 pseudoprimo na base $b$, ent\u00e3o $\\mbox{mdc}(n,b)=1$.<\/div>\n

Com a seguinte fun\u00e7\u00e3o em Python d\u00e1 para verificar se um n\u00famero \u00e9 pseudoprimo para a base $b$.<\/p>\n

\ndef PseudoPrimo( n, b ):\n    return ExpModN( b, n-1, n ) == 1\n<\/code>\n<\/pre>\n
Dado um n\u00famero $n\\in\\N$. Para testar se $n$ \u00e9 primo ou composto, podemos testar se $n$ \u00e9 pseudopromo para algumas bases $b\\in\\{2,\\ldots,n-1\\}$. Se $n$ n\u00e3o for pseudoprimo para uma destas bases, d\u00e1 para concluir que $n$ \u00e9 composto. Caso contr\u00e1rio, o teste \u00e9 inconclusivo.<\/p>\n
Na primeira vers\u00e3o do teste, testamos se $n$ for pseudoprimo para as bases entre $2$ e $2\\log n$. O n\u00famero $2\\log n$ \u00e9 arbitr\u00e1rio e pode ser mudado, mas para um teste eficiente, o n\u00famero de bases testadas precisa ser proporcional com o n\u00famero de algarismos de $n$; ou seja, proporcional com $\\log n$.<\/p>\n
\ndef TesteFermat( n ):\n    \n    d = 2*int(log( n ))+1\n    for b in range( 2, d ):\n        if not PseudoPrimo( n, b ):\n            return "COMPOSTO"\n    return "PROVAVELMENTE PRIMO"\n<\/code>\n<\/pre>\n
Vamos testar quais s\u00e3o os n\u00fameros compostos entre 2 e um milh\u00e3o que n\u00e3o s\u00e3o identificados como compostos usando este teste.<\/p>\n
\nfor n in range( 2, 1000000 ):\n    if TesteFermat( n ) == "PROVAVELMENTE PRIMO" and not isprime( n ):\n        print( n )\n252601\n294409\n399001\n410041\n488881\n512461\n<\/code>\n<\/pre>\n
Em uma outra variante do teste de Fermat, podemos escolher as bases aleatoriamente entre $2$ e $2\\log n$.<\/p>\n
\ndef TesteFermatRandom( n ):\n    \n    d = 2*int(log( n ))+1\n    for i in range( 1, d ):\n        b = random.randint( 2, n-2 )\n        if not PseudoPrimo( n, b ):\n            return "COMPOSTO"\n    return "PROVAVELMENTE PRIMO"\n<\/code>\n<\/pre>\n
Vamos identificar agora os n\u00fameros compostos entre 2 e 1000000 que n\u00e3o s\u00e3o identificados como compostos. Note que como o procedimento \u00e9 aleat\u00f3rio, estes n\u00fameros ser\u00e3o diferentes cada vez que rodarmos a computa\u00e7\u00e3o.<\/p>\n
\nfor n in range( 5, 1000000 ):\n    if TesteFermatRandom( n ) == "PROVAVELMENTE PRIMO" and not isprime( n ):\n        print( n )\n294409\n334153\n488881\n<\/code>\n<\/pre>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
Para um primo $p$, o Pequeno Teorema de Fermat afirma que \\begin{align*} a^p&\\equiv a\\pmod p\\quad\\mbox{para todo}\\quad a\\in \\Z;\\\\ a^{p-1}&\\equiv 1\\pmod p\\quad\\mbox{para todo}\\quad a\\in \\Z\\mbox{ tal que }p\\nmid a. \\end{align*} O Pequeno Teorema de Fermat pode ser usado para dar um crit\u00e9rio suficiente para decidir se um n\u00famero \u00e9 composto. Assuma que $n\\geq 2$ \u00e9 um … Continue reading Teste de primalidade de Fermat<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1193,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1486"}],"collection":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/comments?post=1486"}],"version-history":[{"count":8,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1486\/revisions"}],"predecessor-version":[{"id":1995,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1486\/revisions\/1995"}],"up":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1193"}],"wp:attachment":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/media?parent=1486"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}