1.26: Computación de amod m
- Page ID
- 117451
Primero consideremos la pregunta: ¿Cuál es el menor número de multiplicaciones requeridas para calcular\(a^N\) dónde\(N\) está algún entero positivo?
Supongamos que queremos calcular\(2^8\). Una forma es realizar las siguientes\(7\) multiplicaciones:\[\begin{aligned} 2^2 &=2\cdot 2=4; \\ 2^3 &=2\cdot 4=8; \\ 2^4 &=2\cdot 8=16; \\ 2^5 &=2\cdot 16=32; \\ 2^6 &=2\cdot 32=64; \\ 2^7 &=2\cdot 64=128; \\ 2^8 &=2\cdot 128=256.\end{aligned}\] Pero podemos hacerlo solo en\(3\) multiplicaciones:\[\begin{aligned} 2^2 &=2\cdot 2=4; \\ 2^4 &=\left(2^2\right)^2=4\cdot 4=16; \\ 2^8 &=\left(2^4\right)^2=16\cdot 16=256.\end{aligned}\] En general, usar los pasos del primer método\[a^2=a\cdot a, \quad a^3=a^2\cdot a, \quad a^4=a^3\cdot a, \quad \dotsc, \quad a^n=a^{n-1}\cdot a\nonumber \] requiere\(n-1\) multiplicaciones para calcular\(a^n\).
Por otro lado, si\(n=2^k\) entonces podemos computar\(a^n\) por cuadratura sucesiva con sólo\(k\) multiplicaciones:\[\begin{aligned} a^2 &=a\cdot a \\ a^{2^2} &=\left(a^2\right)^2=a^2\cdot a^2 \\ a^{2^3} &=\left(a^{2^2}\right)^2=a^{2^2}\cdot a^{2^2} \\ \vdots \quad & \qquad \vdots \\ a^{2^k} &=\left(a^{2^{k-1}}\right)^2=a^{2^{k-1}}\cdot a^{2^{k-1}}\end{aligned}\] Obsérvese que el hecho de que\[2^k=\left(2^{k-1}\right)2=2^{k-1}+2^{k-1},\nonumber \] junto con las leyes exponentes\[\left(a^n\right)^m=a^{nm}\nonumber \] y\[a^n\cdot a^m=a^{n+m},\nonumber \] es lo que hace funcionar este método. Tenga en cuenta que si\(n=2^k\) entonces\(k\) es generalmente mucho más pequeño que\(n-1\). Por ejemplo,\[1024=2^{10}\nonumber \] y\(10\) es bastante más pequeño que\(1023\).
Si no\(n\) es un poder de\(2\) podemos usar el siguiente método para calcular\(a^n\).
El método binario para la exponenciación
Dejar\(n\) ser un entero positivo. \(x\)Sea cualquier número real. Este es un método para la computación\(x^n\).
- Paso 1. Encuentra la representación binaria\[n=\left[a_r,a_{r-1},\dotsc,a_0\right]_2\nonumber \] para\(n\).
- Paso 2. Calcule las potencias\[x^2,x^{2^2},x^{2^3},\dotsc,x^{2^r}\nonumber \] por cuadratura sucesiva como se muestra arriba.
- Paso 3. Calcular el producto\[x^n=x^{a_r2^r}\cdot x^{a_{r-1}2^{r-1}}\dotsm x^{a_12}\cdot x^{a_0}.\nonumber \] [Note cada uno\(a_i\) es\(0\) o\(1\), así se obtuvieron todos los factores necesarios en el Paso 2.]
Vamos a calcular\(3^{15}\). Tenga en cuenta que\(15=2^3+2^2+2+1=[1,1,1,1]_2\). Entonces esto se encarga de Step\(1\). Para Step\(2\), observamos\[\begin{aligned} 3^2 &=3\cdot 3=9; \\ 3^{2^2} &=9\cdot 9=81; \\ 3^{2^3} &=81\cdot 81=6561.\end{aligned}\] que So\(3^{15}=3^{2^3}\cdot 3^{2^2}\cdot 3^2\cdot 3^1\). Para ello necesitamos\(3\) multiplicaciones:\[\begin{gathered} 3\cdot 3^2=3\cdot 9=27; \\ \left(3\cdot 3^2\right)\cdot 3^{2^2}=27\cdot 81=2187; \\ \left(3\cdot 3^2\cdot 3^{2^2}\right) 3^{2^3}=2187\cdot 6561=14348907. \label{computation}\end{gathered}\] Entonces tenemos\[3^{15}=14348907.\nonumber \] Tenga en cuenta que hemos usado solo\(6\) multiplicaciones, que es menor que la\(14\) que tomaría si usáramos el método ingenuo. No olvidemos que se necesitó algún esfuerzo adicional para computar la representación binaria de\(15\), pero no mucho.
La computación\(x^n\) usando el método binario requiere\(\lfloor\log_2(n)\rfloor\) aplicaciones del Algoritmo de División y como máximo\(2\lfloor\log_2(n)\rfloor\) multiplicaciones.
Prueba
Si\(n=\left[a_r,\dotsc,a_0\right]_2\),\(a_r=1\), entonces\(n=2^r+\dotsb+a_12+a_0\). De ahí\[2^r\le n\le 2^r+2^{r-1}+\dotsb+2+1=2^{r-1}-1<2^{r+1}.\nonumber \] Desde\(\log_2\left(2^x\right)=x\) y cuando\(0<a<b\) tenemos\(\log_2(a)<\log_2(b)\), las desigualdades por encima de rendimiento\[\log_2\left(2^r\right)\le\log_2(n)<\log_2\left(2^{r+1}\right)\nonumber \] o\[r\le\log_2(n)<r+1.\nonumber \] Por lo tanto\(r=\lfloor\log_2(n)\rfloor\). Tenga en cuenta que\(r\) es el número de veces que necesitamos aplicar el Algoritmo de División para obtener la representación binaria\(n=\left[a_r,\dotsc,a_0\right]_2\),\(a_r=1\). Para calcular las potencias\(x,x^2,x^{2^2},\dotsc,x^{2^r}\) por cuadratura sucesiva se requieren\(r=\lfloor\log_2(n)\rfloor\) multiplicaciones y de manera similar para calcular el producto se\[x^{2^r}\cdot x^{a_{r-1}2^{r-1}}\dotsm x^{a_12}\cdot x^{a_0}\nonumber \] requieren\(r\) multiplicaciones. Entonces después de obtener la representación binaria necesitamos a lo sumo\(2r=2\lfloor\log_2(n)\rfloor\) las multiplicaciones.
Uso de una calculadora para calcular\(\log_2(x)\)
Para encontrar\(\log_2(x)\) uno puede usar la fórmula\[\log_2(x)=\frac1{\ln(2)}\,\ln(x)\nonumber \] o\[\log_2(x)\approx\frac1{0.69314718}\,\ln(x) \approx 1.442695\,\ln(x),\nonumber \] donde\(\ln(x)\) está el logaritmo natural de\(x\). Para valores pequeños de la\(x\) misma a veces es más rápido usar el hecho de que\(r=\lfloor\log_2(x)\rfloor\) es equivalente a\[2^r\le x<2^{r+1},\nonumber \] eso es,\(r\) es el mayor entero positivo tal que\(2^r\le x\).
Obsérvese que si contamos una aplicación del Algoritmo de División y una multiplicación como la misma, lo anterior nos dice que necesitamos como máximo\(3\lfloor\log_2(n)\rfloor\) operaciones para calcular\(x^n\). Entonces, por ejemplo\(n=10^6\), si, entonces es fácil verlo\(3\lfloor\log_2(n)\rfloor=57\). Por lo que podemos calcular solo\(x^{1,000,000}\) con\(57\) operaciones.
Computación\(a^n\bmod m\)
Usamos el método binario para la exponenciación con el truco agregado que después de cada multiplicación reducimos módulo\(m\), es decir, dividimos por\(m\) y tomamos el resto. Esto evita que los productos se hagan demasiado grandes.
Calculamos\(3^{15}\bmod 10\):\[\begin{gathered} \begin{aligned} 3^2 &=3\cdot 3=9\equiv 9\pmod{10}; \\ 3^4 &=9\cdot 9=81\equiv 1\pmod{10}; \\ 3^8 &\equiv 1\cdot 1\equiv 1\equiv 1\pmod{10}; \end{aligned} \\ \therefore 3^{15}=3^8\cdot 3^4\cdot 3^2\cdot 3^1\equiv 1\cdot 1\cdot 9\cdot 3=27\equiv 7\pmod{10}.\end{gathered}\] Tenga en cuenta que eso\(3^{15}\equiv 7\pmod{10}\) implica\(3^{15}\bmod 10=7\). (Recordemos que calculamos aquello\(3^{15}=14348907\) que es claramente congruente con\(7\bmod{10}\), pero las multiplicaciones no fueron tan fáciles).
Vamos a encontrar\(2^{644}\bmod{645}\). Es fácil ver que\[644=[1,0,1,0,0,0,0,1,0,0]_2 .\nonumber \] Eso es,\(644=2^9+2^7+2^2=512+128+4\). Ahora por escuadra sucesiva y reducción de módulo\(645\) obtenemos\[\begin{aligned} 2^2 &=2\cdot 2=4\equiv 4\pmod{645}; \\ 2^4 &\equiv 4\cdot 4=16\equiv 16\pmod{645}; \\ 2^8 &\equiv 16\cdot 16=256\equiv 256\pmod{645}; \\ 2^{16} &\equiv 256\cdot 256=65,536\equiv 391\pmod{645}; \\ 2^{32} &\equiv 391\cdot 391=152,881\equiv 16\pmod{645}; \\ 2^{64} &\equiv 16\cdot 16=256\equiv 256\pmod{645}; \\ 2^{128} &\equiv 256\cdot 256=65,536\equiv 391\pmod{645}; \\ 2^{256} &\equiv 391\cdot 391=152,881\equiv 16\pmod{645}; \\ 2^{512} &\equiv 16\cdot 16=256\equiv 256\pmod{645}.\end{aligned}\] Ahora de\[2^{644}=2^{512}\cdot 2^{128}\cdot 2^4,\nonumber \] ahí\[2^{644}\equiv256\cdot 391\cdot 16\pmod{645}.\nonumber \]\[121\cdot 16=1936\equiv 1\pmod{645},\nonumber \] Así\[256\cdot 391=100099\equiv 121\pmod{645}\nonumber \] y así tenemos\(2^{644}\equiv 1\pmod{645}\). De ahí\(2^{644}\bmod 645=1\).
Ejercicios
Calcular\(3\lfloor\log_2(n)\rfloor\) para\(n=\text{2,000,000}\).
Usa el método binario para calcular\(2^{25}\).
Aproximadamente, ¿cuántas operaciones se requerirían para calcular\(2^n\) cuándo\(n=10^{100}\)? Explique.
Tenga en cuenta que\(6\) las multiplicaciones se utilizan para calcular\(3^{15}\) usando el método binario. Demuestre que se puede calcular\(3^{15}\) con menos de\(6\) multiplicaciones. (Tendrás que experimentar.)
Calcular\(2^{513}\bmod 10\).
Calcular\(2^{517}\bmod 100\).
Si multiplicas\(2^{517}\), ¿cuántos dígitos decimales obtendrías? (Ver Ejercicio 1.6.9.)
Tenga en cuenta que calculamos\(1234^{7865435}\bmod 11\) con muy pocas multiplicaciones. ¿Por qué no podemos usar ese método para calcular\(1234^{7865435}\bmod 12\)?