{"id":1499,"date":"2021-12-14T08:05:36","date_gmt":"2021-12-14T11:05:36","guid":{"rendered":"http:\/\/localhost\/?page_id=1499"},"modified":"2023-01-06T14:49:10","modified_gmt":"2023-01-06T17:49:10","slug":"o-teste-de-primalidade-de-miller","status":"publish","type":"page","link":"http:\/\/localhost\/index.php\/ensino\/fundamentos-de-algebra\/o-teste-de-primalidade-de-miller\/","title":{"rendered":"O Teste de primalidade de Miller"},"content":{"rendered":"
\n
\n(Miller<\/a>, 1976)
\nSeja $n$ um n\u00famero \u00edmpar $n\\geq 3$ e $b\\in\\{1,\\ldots,n-1\\}$. Seja $n-1=2^kq$ onde $k\\geq 1$ e $q$ \u00e9 \u00edmpar. Se $n$ for primo, ent\u00e3o ou $b^q\\equiv 1\\pmod n$, ou
\n\\[
\nb^{2^iq}\\equiv -1\\pmod n\\quad\\mbox{para algum} \\quad i=0,\\ldots,k-1.
\n\\]<\/div>\n
\nComo $n$ \u00e9 \u00edmpar, $n-1$ \u00e9 par e $n-1$ pode ser escrito como $n-1=2^kq$ com $k\\geq 1$ e $q$ \u00edmpar. Assuma que $n$ \u00e9 primo. Pelo Pequeno Teorema de Fermat,
\n\\[
\nb^{n-1}=(b^{q})^{2^k}\\equiv 1\\pmod n.
\n\\]
\nIsto quer dizer que, pelo menos um termo na sequ\u00eancia
\n\\[
\nb^q,\\ (b^q)^2,\\ (b^q)^4,\\ldots,(b^q)^{2^k}
\n\\]
\n\u00e9 congruente com $1$ m\u00f3dulo $n$. Assuma que $j\\geq 0$ \u00e9 o menor \u00edndice tal que
\n\\[
\n(b^q)^{2^j}\\equiv 1\\pmod n.
\n\\]
\nSe $j=0$, ent\u00e3o $b^q\\equiv 1\\pmod n$ e a primeira alternativa do teorema est\u00e1 v\u00e1lida. Se $j\\geq 1$, ent\u00e3o $(b^q)^{2^j}\\equiv 1\\pmod n$ \u00edmplica que
\n\\[
\n(b^q)^{2^j}-1=((b^q)^{2^{j-1}}-1)((b^q)^{2^{j-1}}+1)
\n\\]
\n\u00e9 divis\u00edvel por $n$. Como $n$ \u00e9 primo, um dos fatores $(b^q)^{2^{j-1}}-1$ ou $(b^q)^{2^{j-1}}+1$ precisa ser divis\u00edvel por $n$. Mas, pela minimalidade de $j$, o n\u00famero $n$ n\u00e3o divide $(b^q)^{2^{j-1}}-1$, e isso significa que $(b^q)^{2^{j-1}}+1$ \u00e9 divis\u00edvel por $n$. Mas isso \u00e9 equivalente a afirma\u00e7\u00e3o que $(b^q)^{2^{j-1}}\\equiv -1\\pmod n$.<\/div>\n
\nSeja $n=21$ e seja $b=2$. Escreva $21-1=20=2^2\\cdot 5$. Podemos calcular que $2^5=32\\equiv 11$ e $2^{2\\cdot 5}\\equiv 16\\pmod{21}$. Temos ent\u00e3o que o a conclus\u00e3o do teorema anterior n\u00e3o est\u00e1 v\u00e1lida e assim $21$ n\u00e3o \u00e9 primo.<\/div>\n

O Teorema acima pode ser usado para criar um teste de primalidade um pouco mais sofisticado que o Teste de Fermat.<\/p>\n

\nSeja $n$ um n\u00famero natural \u00edmpar, $n\\geq 3$ e escreva $n-1=2^kq$ onde $k\\geq 1$ e $q$ \u00e9 \u00edmpar. Seja $b\\in\\{2,\\ldots,n-1\\}$. O n\u00famero $n$ \u00e9 dito pseudoprimo forte para a base $b$ se $b^q\\equiv 1\\pmod n$, ou
\n\\[
\nb^{2^iq}\\equiv -1\\pmod n\\quad\\mbox{para algum} \\quad i=0,\\ldots,k-1.
\n\\]<\/div>\n

O Teorema de Miller acima implica que um n\u00famero primo $p$ \u00e9 pseudoprimo forte para todas as bases $b\\in\\{2,\\ldots,p-1\\}$.<\/p>\n

A seguinte fun\u00e7\u00e3o de Python verifica se um n\u00famero \u00e9 pseudoprimo forte para uma base $b$.<\/p>\n

\ndef PseudoPrimoForte( n, b ):\n    \n    # primeiro escrevemos n - 1 = 2^k*q\n    q = n-1\n    k = 0\n    while q % 2 == 0:\n        q = q\/\/2\n        k = k+1\n    \n    # se b^q \u00e9 congruente com 1 mod n ent\u00e3o True\n    r = ExpModN( b, q, n )\n    if r == 1:\n        return True\n    \n    # se existe algum i entre 0 e k-1 tal que \n    # b^(2^iq) \u00e9 congruente com -1 mod n ent\u00e3o true\n    for i in range( 0, k ):\n        if r == n-1:\n            return True\n        r = r*r % n\n    \n    # caso contr\u00e1rio devolva false\n    return False      \n<\/code>\n<\/pre>\n
Na primeira vers\u00e3o do Teste de Miller, checamos se um n\u00famero $n$ \u00e9 pseudoprimo forte para as bases entre $2$ e $2(\\log n)^2$.<\/p>\n
\ndef TesteMiller( n ):\n        \n    k = min(n-1,int(2*log( n )**2))\n    for b in range( 2, k+1 ):\n        if not PseudoPrimoForte( n, b ):\n            return "COMPOSTO"\n        \n    return "PRIMO (HGR)"\n<\/code>\n<\/pre>\n
\u00c9 interessante notar que se a Hip\u00f3tese Generalizada de Riemann<\/a> (HGR) for verdadeira, o Teste de Miller pode ser usado para obter um teste de primalidade que precisa de tempo polinomial.<\/p>\n
\nSuponha que $n$ \u00e9 um n\u00famero composto \u00edmpar. Ent\u00e3o existe uma base $b\\in\\{2,\\ldots,\\lfloor 2(\\log n)^2\\rfloor\\}$ tal que o n\u00famero $n$ n\u00e3o \u00e9 pseudoprimo forte para a base $b$.<\/div>\n
A veracidade da conjectura seria implicada pela veracidade da HGR que \u00e9 considerada entre os problemas mais dif\u00edceis da matem\u00e1tica. De fato a Hip\u00f3tese de Riemann<\/a> aparece entre o Problemas do Pr\u00eamio Millennium<\/a> e uma solu\u00e7\u00e3o correta para este problema resultaria (al\u00e9m da fama eterna) em um pr\u00eamio de um milh\u00e3o de d\u00f3lares.<\/p>\n
A cota $\\lfloor 2(\\log n)^2\\rfloor$ aparece no trabalho de Bach <\/a>(1990).<\/p>\n
Se a Hip\u00f3tese Generalizada de Riemann<\/a> (HGR) for verificada, o Teste de Miller poder\u00e1 ser usado para obter um teste de primalidade que precisa de tempo polinomial.<\/p>\n
Uma vers\u00e3o probabil\u00edstica do Teste de Miller foi sugerida pelo matem\u00e1tico Michael Rabin<\/a>. Nesta vers\u00e3o, n\u00f3s verificamos se $n$ for pseudoprimo forte para $k$ bases aleat\u00f3rias entre $\\{2,\\ldots,n-2\\}$ e o n\u00famero $k$ faz parte do input. O teste probabil\u00edstico est\u00e1 baseado no seguinte resultado que n\u00f3s apresentamos sem demonstra\u00e7\u00e3o.<\/p>\n
\nSeja $n$ um n\u00famero composto \u00edmpar. Ent\u00e3o a propor\u00e7\u00e3o das bases $b\\in\\{2,\\ldots,n-2\\}$ para os quais $n$ \u00e9 pseudoprimo forte \u00e9 no m\u00e1ximo $1\/4$.<\/div>\n
\ndef TesteMillerRabin( n, k ):\n        \n    for i in range( k ):\n        b = random.randint( 2, n-1 )\n        if not PseudoPrimoForte( n, b ):\n            return "COMPOSTO"\n        \n    return "PROVAVELMENTE PRIMO"\n<\/code>\n<\/pre>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
(Miller, 1976) Seja $n$ um n\u00famero \u00edmpar $n\\geq 3$ e $b\\in\\{1,\\ldots,n-1\\}$. Seja $n-1=2^kq$ onde $k\\geq 1$ e $q$ \u00e9 \u00edmpar. Se $n$ for primo, ent\u00e3o ou $b^q\\equiv 1\\pmod n$, ou \\[ b^{2^iq}\\equiv -1\\pmod n\\quad\\mbox{para algum} \\quad i=0,\\ldots,k-1. \\] Como $n$ \u00e9 \u00edmpar, $n-1$ \u00e9 par e $n-1$ pode ser escrito como $n-1=2^kq$ com $k\\geq 1$ … Continue reading O Teste de primalidade de Miller<\/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\/1499"}],"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=1499"}],"version-history":[{"count":7,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1499\/revisions"}],"predecessor-version":[{"id":1997,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1499\/revisions\/1997"}],"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=1499"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}