Cómo calcular $5^{3^{1000}}\bmod 101$ ?

Question

Acabo de empezar un curso de criptografía, así que no tengo ninguna experiencia en el cálculo de números tan grandes. Evidentemente, no puedo usar una calculadora, porque el número es demasiado grande, así que tengo que calcularlo a mano.

Desde $101$ es un número primo, creo que debería usar aquí el pequeño teorema de Fermat. Encontré algún ejemplo y traté de resolverlo de esta manera, pero no estoy totalmente seguro, si es correcto y si mi enfoque debe ser este.

Calcular $5^{3^{1000}}\bmod 101$ .

En primer lugar creo que debo calcular $3^{1000}\bmod 101$ . A partir del pequeño teorema de Fermat llego a $3^{100}\equiv 1\bmod 101$ .

Así, $1000=x100+0$ y $x=10$ .

$3^{1000}\equiv 3^{999^{10}} = 1 ^{10} \equiv 102\bmod 101 $

Después tengo que calcular $5^{102}\bmod 101$ . De nuevo por Fermat $5^{100}\equiv 1\bmod 101$ .

$$102=100\cdot 1 +2$$

Aquí no estoy seguro de cómo seguir adelante... Creo que mi solución es errónea, pero me encantaría ver vuestras sugerencias y comentarios sobre cómo resolver el problema. ¡Muchas gracias de antemano!

Answer 1

Debe calcular $3^{1000}\mod \varphi(101)=100$ . Aquí no se aplica el pequeño teorema de Fermat, ya que $100$ no es primo, por lo que hay que recurrir al teorema de Euler

Si $(a,n)=1$ entonces $a^{\varphi(n)}=1\mod n$ .

Answer 2

Por el pequeño teorema de Fermat sabemos que $5^{100} \equiv 1 \bmod 101$ .

¿Qué nos dice esto exactamente? Nos dice que los poderes de $5$ cuando se reduce el mod $101$ repetir cada $100$ tiempos.

Así que para saber qué $5^{3^{1000}}$ es mod $101$ realmente tenemos que averiguar qué $3^{1000}$ es mod $100$ .

Puede utilizar la generalización de FlT mencionada en otra respuesta para ver que $3^{40} \equiv 1 \bmod 100$ para que $3^{1000} = (3^{40})^{25} \equiv 1^{25} \equiv 1 \bmod 100$ .

También puedes hacerlo con pequeños cálculos paso a paso.

De cualquier manera, encontramos que $5^{3^{1000}} \equiv 5 \bmod 101$ .

Answer 3

Usted ha visto que $5^{100} \equiv 1 \pmod{101}$ . De ello se desprende que $5^{100a+b} \equiv 5^b \pmod{101}$ . Ahora deberías ver hasta qué módulo tienes que calcular $3^{1000}$ .