Módulo de un número muy grande, Cómo calcular $11386^{20635} \mod 31351$ ?

Question

Tengo problemas para calcular el mod de un número muy grande. He intentado comprobarlo con ejemplos anteriores, pero no lo he entendido.

Por favor, ayúdenme con la siguiente pregunta.
Cómo calcular $$11386^{20635} \mod 31351\;?$$

Answer 1

Compute $\gcd(11386,31351)=1$ utilizando el algoritmo de Euclides.

A continuación, calcule $\phi(31351)=30952$ .

Calcular el resto de $20635$ por división por $30952$ . Esta parte no es importante en este ejemplo concreto porque $20635$ es menor que $30952$ pero puede ser útil en algún otro cálculo.

Se trata de utilizar ese $a^{\phi(b)}=1$ mod $b$ si $\gcd(a,b)=1$ . Esto significa que si desea calcular $a^N$ mod $b$ y $N=\phi(b)\cdot q+r$ entonces $a^N=a{\phi(b)\cdot q+r}=(a^{\phi(b)})^qa^r=a^r$ mod $b$ .

Después de esto sólo tenemos que calcular $a^r$ mod $b$ .

Para terminar puedes utilizar el algoritmo de Cuadrar y Multiplicar. Significado: Calcular $a^2$ y calcular el resto mod $b$ . Elevamos al cuadrado de nuevo y volvemos a calcular el resto, ...

Expresar el número $r$ en base $2$ y eso te dice qué poderes debes multiplicar para conseguir $a^r$ mod $b$ .