Loading [MathJax]/jax/element/mml/optable/BasicLatin.js

132 votos

Exponenciación modular a mano ( abmod )

¿Cómo puedo calcular eficientemente a^b\bmod c :

  • En b es enorme, por ejemplo 5^{844325}\bmod 21 ?
  • En b es inferior a c pero aún así sería mucho trabajo multiplicar a por sí mismo b veces, por ejemplo 5^{69}\bmod 101 ?
  • En (a,c)\ne1 por ejemplo 6^{103}\bmod 14 ?

¿Existen otros trucos para evaluar exponentes en aritmética modular?


Esto se pide en un esfuerzo por reducir los duplicados, véase aquí y aquí .

3 votos

Pequeño teorema de fermat

3 votos

Puede resultar laborioso cuando c es enorme, pero b ser enorme no debería ser un problema.

76voto

Robert Christie Puntos 7323

Wikipágina sobre aritmética modular no está mal.

  • En b es enorme, y a y c son coprimos, Teorema de Euler se aplica: a^b \equiv a^{b \, \bmod \, \phi(c)} \, \bmod c Para el ejemplo que nos ocupa, \phi(21) = \phi(3) \times \phi(7) = 2 \times 6 = 12 . \Rightarrow 844325 \bmod 12 = 5,\ \text{so}\ 5^5 = 5 \times 25^2 \equiv 5 \times 4^2 = 80 \equiv 17 \mod 21 .

  • En a y c son coprimos, pero 0<b<\phi(c) La cuadratura repetida (o el uso de otras composiciones de potencias) es la forma más rápida de hacerlo (manualmente): \begin{eqnarray} 5^4 \equiv 5 \times 5^3 \equiv 5 \times 24 \equiv 19 &\pmod{101}\\ 19^4 \equiv (19^2)^2 \equiv 58^2 \equiv (-43)^2 \equiv 1849 \equiv 31 &\pmod{101} \\ 31^4 \equiv (31^2)^2 \equiv (961)^2 \equiv 52^2 \equiv 2704 \equiv 78 &\pmod{101} \\ 5^{69} \equiv 5 \times 5^4 \times ((5^4)^4)^4 \equiv 5 \times 19 \times 78 \equiv 5 \times 19 \times (-23)\\ \equiv 19 \times (-14) \equiv -266 \equiv 37 & \pmod{101} \end{eqnarray}

  • En a y c no son coprimos, sea g = \gcd(a,c) . Sea a = g \times d y c = g \times f entonces, suponiendo b > 1 : a^b \bmod c = g^b \times d^b \bmod (g \times f) = ( g \times (g^{b-1} d^b \bmod f) ) \bmod c En el ejemplo dado, \gcd(6,14) = 2 . Así que 2^{102} \times 3^{103} \mod 7 utilizando el teorema de Euler, con \phi(7) = 6 y 102 \equiv 0 \mod 6 , 2^{102} \times 3^{103} \equiv 3 \mod 7 Así que 6^{103} \equiv (2 \times 3) \equiv 6 \mod 14 .

18 votos

Función Carmichael suele reducir el exponente más que la función totiente de Euler.

0 votos

En \gcd(a,c)\ne1 se puede resumir el último caso como a^b\equiv a^{(b\bmod\varphi)+\varphi}\pmod c donde \varphi=\varphi(c/\gcd(a^{\lfloor\log_2(c)\rfloor},c)) saca todos los factores comunes a la vez y luego aplica el teorema del totiente de Euler. Como \log_2(c) suele ser muy pequeño, y el algoritmo euclidiano nos permite utilizar la exponenciación modular (elevando al cuadrado), a^{\lfloor\log_2(c)\rfloor} no es un cálculo difícil. Esto tiene la ventaja de que sólo necesitamos calcular el \gcd una vez y evita anidar mods repetidamente.

49voto

Michael Hardy Puntos 128804

Probemos 5^{844325} \bmod 21 : \begin{align} 5^0 & & & \equiv 1 \\ 5^1 & & &\equiv 5 \\ 5^2 & \equiv 25 & & \equiv 4 \\ 5^3 & \equiv 4\cdot 5 & & \equiv 20 \\ 5^4 & \equiv 20\cdot 5 & & \equiv 16 \\ 5^5 & \equiv 16\cdot 5 & & \equiv 17 \\ 5^6 & \equiv 17\cdot 5 & & \equiv 1 \end{align} Así que multiplicando por 5 seis veces es lo mismo que multiplicar por 1 . Queremos multiplicar por 5 un gran número de veces: 844325 . ¿Cuántas veces multiplicamos por 5 ¿Seis veces? El número de veces 6 entra en 844325 es 140720 con un remanente de 5 . Ese resto es lo que importa. Multiplica por 5^6 exactamente 140720 veces y eso es lo mismo que multiplicar por 1 tantas veces. Luego multiplique por 5 sólo 5 más veces, y obtener 17 .

Así que 5^{844325} \equiv 17 \bmod 21 .

0 votos

Puede que quieras comprobar mi aritmética, pero este método lo hará cuando lo hagas bien.

1 votos

Este método no será tan agradable cuando (5,21)\neq 1 ...

8 votos

@aengle: será similar: por ejemplo para 6^{844325} \mod 21 mirarías 6^0 \equiv 1 , 6^1 \equiv 6 , 6^2 \equiv 15 , 6^3 \equiv 6 , 6^4 \equiv 15 por lo que con un periodo de 2 . El número de veces 2 entra en 844325 es 422162 con un remanente de 1 . Así que 6^{844324} \equiv 15 \mod 21 y así 6^{844325} \equiv 6 \mod 21 .

24voto

He aquí dos ejemplos elevar al cuadrado y multiplicar método para 5^{69} \bmod 101 :

\begin{matrix} 5^{69} &\equiv& 5 &\cdot &(5^{34})^2 &\equiv & 37 \\ 5^{34} &\equiv& &&(5^{17})^2 &\equiv& 88 &(\equiv -13) \\ 5^{17} &\equiv& 5 &\cdot &(5^8)^2 &\equiv& 54 \\ 5^{8} &\equiv& &&(5^4)^2 &\equiv& 58 \\ 5^{4} &\equiv& &&(5^2)^2 &\equiv& 19 \\ 5^{2} &\equiv& &&(5^1)^2 &\equiv& 25 \\ 5^{1} &\equiv& 5 &\cdot &(1)^2 &\equiv& 5 \end{matrix}

El cálculo comienza con 5^{69} y luego trabajar hacia abajo para crear las dos primeras columnas, y luego calcular los resultados de abajo hacia arriba. (normalmente se omitiría la última línea; la he puesto ahí para aclarar el párrafo siguiente).

Como método abreviado, la representación binaria de 69 es 1000101_2 la lectura de los dígitos binarios de izquierda a derecha nos indica las operaciones a realizar a partir del valor 1 : 0 dice "cuadrado" y 1 dice "elevar al cuadrado y multiplicar por 5 ".


La otra forma es calcular una lista de cuadrados repetidos:

\begin{matrix} 5^1 &\equiv& 5 \\ 5^2 &\equiv& 25 \\ 5^4 &\equiv& 19 \\ 5^8 &\equiv& 58 \\ 5^{16} &\equiv& 31 \\ 5^{32} &\equiv& 52 \\ 5^{64} &\equiv& 78 \end{matrix}

A continuación, calcula qué términos tienes que multiplicar:

5^{69} \equiv 5^{64 + 4 + 1} \equiv 78 \cdot 19 \cdot 5 \equiv 37

22voto

freespace Puntos 9024

Algunos trucos útiles para la exponenciación modular

La intención de este post es recopilar varios trucos que a veces pueden simplificar los cálculos de este tipo. (Especialmente cuando se hacen a mano y no con ordenador o calculadora.) Este post es comunidad-wiki, así que siéntete libre de editarlo si tienes alguna idea para mejorarlo.

Usar complemento: (c-a) \equiv (-a) \pmod c

Si el número dado se aproxima a c (pero menor que c ), sustituyéndolo por c-a mi ayuda - trabajaremos con números más pequeños. Algunos ejemplos:

  • Si queremos calcular 7^{777} \bmod 50 es útil observar que 7^2=49 \equiv (-1) \pmod{50} por lo que podemos sustituir 7^2 por -1 y obtener 7^{777} \equiv 7^{388} \cdot 7 \equiv (-1)^{388} \cdot 7 \equiv 7 \pmod{50} . (Esto formaba parte de Encuentre 3^{333} + 7^{777}\pmod{50} .)
  • Queremos calcular 50^{50} \bmod 13 . Desde 4\cdot 13 = 52 tenemos 50 \equiv -2 \pmod{13} . Así que podemos trabajar con -2 en lugar de 50 que será más fácil, ya que es un número más pequeño. Cómo utilizar el pequeño teorema de Fermat para hallar 50^{50}\pmod{13} ?

Si puedes encontrar una potencia cercana al módulo, intenta utilizarla.

Algunos ejemplos:

  • Queremos calcular 6^{1000} \bmod 23 . Desde 6=2\cdot 3 veamos si podemos combinar de alguna manera estos dos números para obtener algo con un resto pequeño módulo 23 . Podemos observar que 24=2^3\cdot 3 \equiv 1\pmod{23} . También podemos observar que 27 \equiv 4\pmod{23} es decir 3^3\equiv 2^2\pmod{23} . Sustitución de 2^2 con 3^3 en la congruencia anterior obtenemos 2\cdot 3^4 \equiv 1 \pmod{23} . Ahora podemos combinar las dos congruencias anteriores para obtener 1\equiv (2^3\cdot 3)^3\cdot(2\cdot 3^4)^2 = 2^{11}\cdot3^{11} = 6^{11}\pmod{23} . Obsérvese que la congruencia 6^{11}\equiv1\pmod{23} también puede obtenerse por distintos medios: Encuentre 6^{1000} \mod 23 .
  • Queremos encontrar 5^{119} \bmod 59 . Esto puede resolverse de forma muy sencilla utilizando el pequeño teorema de Fermat: Hallar el resto utilizando el pequeño teorema de Fermat cuando 5^{119} se divide por 59 ? Sin embargo, olvidemos el pequeño teorema de Fermat y tratemos de encontrar algunas potencias de 5 que dan un resto pequeño módulo 59 . Podemos observar que 5^3 no está muy lejos de 2\cdot59 y obtener 5^3\equiv125\equiv7\pmod{59} . Del mismo modo, 7\cdot25 parece no estar muy lejos de 3\cdot59 así que podemos intentar 5^5=5^3\cdot5^2\equiv7\cdot25\equiv175\equiv-2\pmod{59} . Y ahora podemos utilizar 64 es una potencia de dos que se aproxima a nuestro resto para obtener 5^{30} = (5^5)^6 \equiv (-2)^6 \equiv 64 \equiv 5 \pmod{59} . Puesto que tenemos 5^{30}\equiv5\pmod{59} y \gcd(5,59)=1 podemos cancelar 5 en ambos lados para obtener 5^{29}\equiv1\pmod{59} . Y este último dato puede utilizarse en cálculos posteriores.
  • La tarea consiste en encontrar 16^{74} \bmod 65 . Se puede observar que 64 es una potencia de dos muy próxima a 65 . Así que tenemos 2^6 = 64 \equiv -1 \pmod{65} lo que significa que 16^{74}=(2^4)^{74}=2^{296} = 2^{6\cdot49}\cdot2^2 \equiv (-1)^{49}\cdot4 \equiv -1\cdot 4 \equiv -4 \pmod{65} . Ver también Informática 16^{74} \bmod 65 .

Utilizando el criterio de Euler

Criterio de Euler puede decirnos sobre el valor de a^{\frac{p-1}2} módulo de un primo p . Sin embargo, necesitamos saber si a es un residuo cuadrático módulo p . Para algunos números esto se puede adivinar. A veces se puede comprobar utilizando reciprocidad cuadrática (Por supuesto, esto no es una gran mejora en comparación con el pequeño teorema de Fermat, que nos da a^{p-1}\equiv1\pmod p .)

  • Veamos 5^{29} \bmod 59 (ya lo hemos calculado anteriormente mediante diferentes cálculos). Es fácil darse cuenta de que 8^2=64\equiv5\pmod{59} Así que 5 es un residuo cuadrático módulo 59 . Así que a partir del criterio de Euler obtenemos 5^{29}=5^{(59-1)/2}\equiv1\pmod{29} .

14voto

El teorema chino del resto puede reducir el cálculo necesario. Por ejemplo, podemos factorizar 21 = 3 \cdot 7 y tienen

1 \cdot 7 - 2 \cdot 3 = 1

(en general, podemos utilizar el algoritmo euclidiano ampliado para obtener esta fórmula)

Por consiguiente, si

x \equiv a \pmod 3 \qquad x \equiv b \pmod 7

entonces

x \equiv a \cdot (1 \cdot 7 ) + b \cdot (-2 \cdot 3) \pmod{21}

Así, podemos calcular 5^{844325} \bmod 21 utilizando nuestros medios favoritos para calcular:

5^{844325} \equiv 2 \pmod 3 \qquad 5^{844325} \equiv 3 \pmod 7

y así

5^{844325} \equiv 2 \cdot 7 + 3 \cdot (-6) \equiv -4 \equiv 17 \pmod{21}

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X