{"id":969,"date":"2020-09-23T21:40:59","date_gmt":"2020-09-23T21:40:59","guid":{"rendered":"http:\/\/localhost\/?page_id=969"},"modified":"2022-07-04T09:58:32","modified_gmt":"2022-07-04T12:58:32","slug":"numeros-de-carmichael-e-o-teste-de-miller","status":"publish","type":"page","link":"http:\/\/localhost\/index.php\/ensino\/algebra-a\/numeros-de-carmichael-e-o-teste-de-miller\/","title":{"rendered":"N\u00fameros de Carmichael e o Teste de Miller"},"content":{"rendered":"

Seja $n$ um n\u00famero natural com $n\\geq 5$ e seja $a\\in\\{2,\\ldots,n-2\\}$. Lembre que $n$ \u00e9 dito pseudoprimo na base $a$ se $a^{n-1}\\equiv 1\\pmod n$. Observe que se $n$ for pseudoprimo na base $a$, ent\u00e3o $a^n\\equiv a\\pmod n$.<\/p>\n

Um n\u00famero composto $n$ \u00e9 dito n\u00famero de Carmichael se $a^n\\equiv a\\pmod n$ para todo $a\\in\\{1,\\ldots,n-1\\}$.<\/p>\n

\nMostre que um n\u00famero de Carmichael \u00e9 \u00edmpar.\n<\/div>\n

N\u00fameros de Carmichael s\u00e3o os mais prov\u00e1veis de passarem no teste de primalidade de Fermat, pois se $n$ \u00e9 de Carmichael, ent\u00e3o $b^{n-1}\\equiv 1\\pmod n$ vale para qualquer base $b$ coprimo com $n$. Ou seja, $n$ ser\u00e1 pseudoprimo para muitas bases.<\/p>\n

O menor n\u00famero de Carmichael \u00e9 561. Usando a defini\u00e7\u00e3o de n\u00fameros de Carmichael, este fato n\u00e3o \u00e9 f\u00e1cil de verificar sem usar um computador. No entanto, a verifica\u00e7\u00e3o pode ser feita sabendo que
\n\\[
\n561=3\\cdot 11\\cdot 17.
\n\\]
\nSeja $b\\in\\{1,\\ldots,560\\}$ arbitr\u00e1rio. N\u00f3s vamos mostrar que $b^{561}\\equiv b\\pmod{561}$. Esta congru\u00e9ncia \u00e9 equivalente ao fato que $561\\mid (b^{561}-b)$. Para provar esta divisibilidade, basta verificar que $3$, $11$, e $17$ s\u00e3o divisores de $b^{561}-b$ para todo $b\\in\\{1,\\ldots,560\\}$.<\/p>\n

Primeiro tratamos a afirma\u00e7\u00e3o que $17\\mid (b^{561}-b)$; ou seja
\n\\[
\nb^{561}\\equiv b\\pmod {17}.
\n\\]
\nSe $17\\mid b$, ent\u00e3o os dois lados da congru\u00eancia s\u00e3o congruentes com zero, ent\u00e3o n\u00e3o h\u00e1 nada para fazer. Assuma que $17\\nmid b$. Neste caso, o Pequeno Teorema de Fermat d\u00e1 que $b^{16}\\equiv 1\\pmod{17}$ e isso implica que
\n\\[
\nb^{560}=(b^{16})^{35}\\equiv 1\\pmod{17}.
\n\\]
\nObtemos assim que $b^{561}\\equiv b\\pmod{17}$ ou seja $17\\mid( b^{561}-b)$.<\/p>\n

Notando que $560=561-1$ \u00e9 divis\u00edvel por $3-1=2$ e por $11-1=10$, as divisibilidades $3\\mid (b^{561}-b)$ e $11\\mid (p^{561}-b)$ podem ser verificadas similarmente.<\/p>\n

Observe que na conta acima os fatos cruciais sobre o n\u00famero 561 foram os seguintes:<\/p>\n

    \n
  1. o n\u00famero 561 \u00e9 livre de quadrado; ou seja, ele n\u00e3o \u00e9 divis\u00edvel por $p^2$ para nenhum primo $p$;<\/li>\n
  2. se $p$ divide 561, ent\u00e3o $p-1$ divide 560.<\/li>\n<\/ol>\n

    Acontece que estes dois fatos de fato s\u00e3o necess\u00e1rios e suficientes para um n\u00famero ser de Carmichael.<\/p>\n

    \n(Korselt<\/a>) Seja $n\\geq 2$ um n\u00famero natural\u00a0 composto. Ent\u00e3o $n$ \u00e9 um n\u00famero de Carmichael (ou seja, $b^n\\equiv b\\pmod n$ para todo $b\\in\\{1,\\ldots,n-1\\}$) se e somente se as seguintes propriedades s\u00e3o v\u00e1idas:<\/p>\n
      \n
    1. $n$ \u00e9 livre de quadrado ($n$ n\u00e3o \u00e9 divis\u00edvel por $p^2$ para nenhum primo $p$);<\/li>\n
    2. se $p$ \u00e9 um primo que divide $n$, ent\u00e3o $p-1$ divide $n-1$.<\/li>\n<\/ol>\n

      Vamos agora estudar um teste de primalidade que funciona melhor at\u00e9 com n\u00fameros de Carmichael.\n<\/p><\/div>\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\\]\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 lema est\u00e1 v\u00e1lida. Se $j\\geq 1$, ent\u00e3o $(b^q)^{2^j}\\equiv 1$ \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$.\n<\/div>\n

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

      Algoritmo: TesteMiller<\/strong> Teste de de primalidade Miller<\/span>
      \nInput:<\/strong> N\u00famero natural $n$ \u00edmpar e $b$ entre $2$ e $n-1$.<\/span><\/p>\n

      Escreva $n-1=2^kq$ com $q$ \u00edmpar<\/div>\n
      $r := b^q\\pmod n$<\/div>\n
      Se $r\\equiv 1\\pmod n$ ent\u00e3o<\/div>\n
      Devolve TALVEZ PRIMO<\/div>\n
      Fa\u00e7a para $j=0,\\ldots,k-1$<\/div>\n
      Se $r\\equiv -1\\pmod n$ ent\u00e3o<\/div>\n
      Devolve TALVEZ PRIMO<\/div>\n
      $r := r^2\\pmod n$<\/div>\n
      Devolva COMPOSTO<\/div>\n

       <\/p>\n

      Claramente, a confiabilidade to Teste de Miller pode ser melhorada se executarmos o teste com v\u00e1rias bases $b$. \u00c9 interessante notar que se a Hip\u00f3tese Generalizada de Riemann<\/a>\u00a0(HGR) for verdadeira, o Teste de Miller pode ser usado para obter um teste de probabilidade que precisa de tempo polinomial.<\/p>\n

      Conjectura.<\/strong>\u00a0Suponha que\u00a0$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 passa no Teste de Miller na base $b$.<\/p>\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>\u00a0e uma solu\u00e7\u00e3o correta para este problema resultaria (al\u00e9m da fama eterna) 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\u00a0<\/a>(1990).\u00a0<\/strong>Assumindo a veracidade da HGR, o seguinte algoritmo determine se um n\u00famero \u00e9 primo ou composto.<\/p>\n

      Algoritmo: TesteMillerBach<\/strong> Teste de de primalidade Miller-Bach<\/span>
      \nInput:<\/strong> N\u00famero natural $n$ \u00edmpar<\/span><\/p>\n

      Fa\u00e7a para $b=2,\\ldots,\\lfloor2( \\log n)^2\\rfloor$<\/div>\n
      Se TesteMiller$( n, b )$ \u00e9 COMPOSTO ent\u00e3o<\/div>\n
      Devolve COMPOSTO<\/div>\n
      Devolva PRIMO<\/div>\n

       <\/p>\n","protected":false},"excerpt":{"rendered":"

      Seja $n$ um n\u00famero natural com $n\\geq 5$ e seja $a\\in\\{2,\\ldots,n-2\\}$. Lembre que $n$ \u00e9 dito pseudoprimo na base $a$ se $a^{n-1}\\equiv 1\\pmod n$. Observe que se $n$ for pseudoprimo na base $a$, ent\u00e3o $a^n\\equiv a\\pmod n$. Um n\u00famero composto $n$ \u00e9 dito n\u00famero de Carmichael se $a^n\\equiv a\\pmod n$ para todo $a\\in\\{1,\\ldots,n-1\\}$. Mostre que … Continue reading N\u00fameros de Carmichael e o Teste de Miller<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":706,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/969"}],"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=969"}],"version-history":[{"count":11,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/969\/revisions"}],"predecessor-version":[{"id":1852,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/969\/revisions\/1852"}],"up":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/706"}],"wp:attachment":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/media?parent=969"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}