{"id":1507,"date":"2021-12-14T09:16:49","date_gmt":"2021-12-14T12:16:49","guid":{"rendered":"http:\/\/localhost\/?page_id=1507"},"modified":"2023-01-06T14:48:29","modified_gmt":"2023-01-06T17:48:29","slug":"o-algoritmo-da-exponenciacao-rapida","status":"publish","type":"page","link":"http:\/\/localhost\/index.php\/ensino\/fundamentos-de-algebra\/o-algoritmo-da-exponenciacao-rapida\/","title":{"rendered":"O Algoritmo da Exponencia\u00e7\u00e3o R\u00e1pida"},"content":{"rendered":"
\nNas v\u00e1rias computa\u00e7\u00f5es relacionadas com congru\u00eancias n\u00f3s precisamos calcular $a^k$ m\u00f3dulo $n$ para n\u00fameros $a$, $k$, $n$ que s\u00e3o grandes com centenas ou milhares de d\u00edgitos. Nestes casos multiplicar $k$ vezes o n\u00famero $a$ e tomar o resto do resultado m\u00f3dulo $n$ n\u00e3o pode ser feito.<\/p>\n

Assuma que $k=[k_m\\cdots k_1k_0]_2$; ou seja,
\n\\[
\nk=2^mk_m+2^{m-1}k_{m-1}+\\cdots+2k_1+k_0.
\n\\]
\nEnt\u00e3o
\n\\[
\na^k=a^{2^mk_m+2^{m-1}k_{m-1}+\\cdots+2k_1+k_0}=\\prod_{i=0}^m a^{2^ik_i}=\\prod_{k_i\\neq 0} a^{2^i}.
\n\\]<\/p>\n

Note que as pot\u00eancias $a,a^2,a^4,a^8,\\ldots$ (m\u00f3dulo $n$) podem ser computadas como $a^{2^{i+1}}=(a^{2^i})^2$ e calcular a sequ\u00eancia $a,a^2,\\ldots,a^{2^m}$ m\u00f3dulo $n$ precisa de $m-1$ multiplica\u00e7\u00f5es e $m-1$ divis\u00f5es euclidianas. Depois multiplicar estas pot\u00eancias na ordem certa precisa de no m\u00e1ximo $m-1$ multiplica\u00e7\u00f5es e $m-1$ divis\u00f5es euclidianas.<\/p>\n

Ent\u00e3o $a^k\\pmod n$ pode ser calculado usando no m\u00e1ximo $2m-2$ multiplica\u00e7\u00f5es e divis\u00f5es euclidianas onde $m=\\lfloor \\log_2 k\\rfloor$.<\/p>\n

\nVamos calcular os \u00faltimos 2 d\u00edgitos de $2^{81}$. Para isso, precisamos calcular $2^{81}\\pmod{100}$. Como
\n\\[
\n81=[1010001]_2=64+16+1
\n\\]
\nprecisamos determinar $2,2^2,2^4,2^8,2^{16},2^{32},2^{64}$ m\u00f3dulo $100$. Cada termo desta sequ\u00eancia pode ser determinado como o quadrado do termo anterior e tomar o resto m\u00f3dulo $100$:
\n\\begin{align*}
\n2&\\equiv 2,\\quad 2^2\\equiv 4,\\quad 2^4\\equiv 16,\\quad 2^8\\equiv 56, \\\\
\n2^{16}&\\equiv 36,\\quad 2^{32}\\equiv 96,\\quad 2^{64}\\equiv 16\\pmod{100}.
\n\\end{align*}
\nLogo
\n\\[
\n2^{81}\\equiv 2^{1}\\cdot 2^{16}\\cdot 2^{64}=2\\cdot 36\\cdot 16\\equiv 52\\pmod{100}.
\n\\]<\/div>\n

O algoritmo que obtemos assim \u00e9 chamado Algoritmo de Exponencia\u00e7\u00e3o (Potencia\u00e7\u00e3o) R\u00e1pida, ou Algoritmo de Exponencia\u00e7\u00e3o (Potencia\u00e7\u00e3o) Modular.<\/p>\n

A seguinte fun\u00e7\u00e3o em Python implementa o Algoritmo de Exponencia\u00e7\u00e3o R\u00e1pida.<\/p>\n

\ndef ExpModN( a, k, n ):\n    A = a; P = 1; K = k;\n    \n    while K != 0:\n        \n        D = K % 2 \n        #o \u00faltimo d\u00edgito de K  \n        if D == 1: \n            P = (A*P) % n\n            K = (K-1)\/\/2\n        else:\n            K = K\/\/2\n        A = A*A % n\n    return P\n<\/code>\n<\/pre>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
Nas v\u00e1rias computa\u00e7\u00f5es relacionadas com congru\u00eancias n\u00f3s precisamos calcular $a^k$ m\u00f3dulo $n$ para n\u00fameros $a$, $k$, $n$ que s\u00e3o grandes com centenas ou milhares de d\u00edgitos. Nestes casos multiplicar $k$ vezes o n\u00famero $a$ e tomar o resto do resultado m\u00f3dulo $n$ n\u00e3o pode ser feito. Assuma que $k=[k_m\\cdots k_1k_0]_2$; ou seja, \\[ k=2^mk_m+2^{m-1}k_{m-1}+\\cdots+2k_1+k_0. \\] … Continue reading O Algoritmo da Exponencia\u00e7\u00e3o R\u00e1pida<\/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\/1507"}],"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=1507"}],"version-history":[{"count":14,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1507\/revisions"}],"predecessor-version":[{"id":1994,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1507\/revisions\/1994"}],"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=1507"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}