¿Cómo se calcula el módulo de un número elevado?

Question

Necesito ayuda con este problema:

$$439^{233} \mod 713$$

No puedo calcular $439^{223}$ ya que es un número muy grande, debe haber una manera de hacer esto.

Gracias.

Answer 1

A menudo hay trucos para esto si los números son lo suficientemente buenos, pero incluso si no lo son, aquí hay una manera que no es totalmente horrible.

Ya sabes lo que es el 439 mod 713. ¿Qué es $439^2 \mod 713$ ? ¿Qué pasa con $439^4$ ? (Pista: tome su respuesta para $439^2$ después de reduciéndolo mod 713, y volviéndolo a cuadrar). De la misma manera, calcula $439^8, 439^{16}, \dots, 439^{128} \mod 713$ . Ahora sólo hay que tener en cuenta que 233 = 128 + 64 + 32 + 8 + 1. Así que multiplica las potencias apropiadas de 439 juntas - de nuevo, un cálculo a la vez, reduciendo mod 713 cada vez.

Ahora sólo deberías tener que hacer 11 cálculos, y ahora todos tus números tienen 6 dígitos o menos. Más que imposible, ahora es simplemente tedioso. :)

Por cierto, una cosa a tener en cuenta: 713 = 23 * 31. Quizás tus cálculos sean más fáciles si los haces mod 23 y 31, y luego aplicas la Teorema del resto chino ?

Answer 2

$713=23\cdot 31$

$439 \pmod {23}=2$ y $\phi(23)=22$ y $233\equiv 13{\pmod {22}}$

Así que, $439^{223} {\pmod {23}} \equiv 2^{22\cdot 10 + 13}\equiv {(2^{22})}^{10}2^{13}\equiv 2^{13} {\pmod {23}}$ utilizando Teorema del Totiente de Euler .

$2^6\equiv 18 {\pmod {23}}, 2^7\equiv 36 \equiv 13$

$\implies 2^{13}\equiv 18\cdot 13=234\equiv 4 {\pmod {23}}=4+23x$ para algún número entero $x$ .

$439 \pmod {31}=5$ y $\phi(31)=30$ y $233\equiv 23{\pmod {30}}$

Así que, $439^{223} {\pmod {31}} \equiv 5^{23} {\pmod {31}}$

$5^3 \equiv 1 {\pmod {31}} \implies 5^{23}\equiv({5^3})^7 5^2\equiv 5^2{\pmod {31}}=25+31y$ para algún número entero $y$ .

Por lo tanto, tenemos que encontrar $z$ tal que $z=25+31y=4+23x$

Expresando como fracción continua , $$\frac{31}{23}=1+\frac{8}{23}=1+\frac{1}{\frac{23}{8}}=1+\frac{1}{2+\frac{7}{8}}$$

$$=1+\frac{1}{2+\frac{1}{\frac{8}{7}}}=1+\frac{1}{2+\frac{1}{1+\frac{1}{7}}}$$

Así, el penúltimo convergente es $$1+\frac{1}{2+\frac{1}{1}}=\frac{4}{3}$$

Así que, $23\cdot 4- 31\cdot 3=-1$

$25+31y=4+23x\implies 23x=31y+21(31\cdot 3-23\cdot 4)$ $\implies 23(x+84)=31(y+63)$ $$\implies x+84=\frac{31(y+63)}{23}$$

Así que, $23\mid (y+63)$ como $x+84$ es un número entero y $(31,23)=1$ es decir, $ 23\mid (y+69-6)\implies 23\mid (y-6) \implies y=6+23w$

Así que, $z=25+31y=25+31(6+31w)=713w+211 \equiv 211 {\pmod {713}}$

Answer 3

Aquí está el algoritmo, básicamente es Exponenciación modular.

function modular_pow(base, exponente, módulo)

result := 1

while exponent > 0
    if (exponent mod 2 == 1):
       result := (result * base) mod modulus
    exponent := exponent >> 1
    base = (base * base) mod modulus
return result

También aquí está el código de trabajo en c ++ que puede trabajar para hasta 10^4 casos de prueba, en 0,7 segundos También el enlace de ideone http://ideone.com/eyLiOP

#include <iostream>
using namespace std;
#define mod 1000000007

long long int modfun(long long int a,long long int b)
{
     long long int result = 1;
    while (b > 0)
       {
           if (b & 1)
           {
               a=a%mod;
               result = (result * a)%mod;
               result=result%mod;
           }
        b=b>>1;
        a=a%mod;
        a = (a*a)%mod;
        a=a%mod;
       }
    return result;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
        {
           long long int a,b;
           cin>>a>>b;
           if(a==0)
            cout<<0<<"\n";
           else if(b==0)
            cout<<1<<"\n";
           else if(b==1)
            cout<<a%mod<<"\n";
           else
           {
               cout<<(modfun(a,b))%mod<<"\n";
           }

        }
    return 0;
}

Answer 4

Se puede ir rápido si se cuadra de forma incremental: $439^2=211 \pmod{713}$ ; $211^2=315 \pmod{713}$ ; $315^2=118 \pmod{713}$ ; $315^2=377 \pmod{713}$ ; $377^2=242 \pmod{713}$ ; $377^2=98 \pmod{713}$ etc.

El último significa $439^{64}=98 \pmod{713}$ ; De este modo, puedes combinar y llegar a 233 rápidamente.

En definitiva, $439^{233}=211 \pmod{713}$ ;

Answer 5

Puedes hacerlo paso a paso calculando primero $439^2\equiv 211 {\ \rm mod\ }713$ . A continuación, se calcula $439^4\equiv 211^2 \equiv 315 {\ \rm mod\ }713$ . Seguir cuadrando y reduciendo el mod $713$ y construir una lista de poderes $$439^1, \qquad 439^2, \qquad 439^4 \qquad \dots \qquad 439^{128}\qquad \qquad ({\rm mod\ }713)$$ Por último, escriba $233$ como una suma de potencias de $2$ y calcular $$439^{233}=439^{1+8+32+64+128}=439\cdot 439^8\cdot 439^{32}\cdot439^{64}\cdot 439^{128} \qquad ({\rm mod\ }713)$$ Sólo recuerde reducir el mod $713$ cada vez que se adquiere un producto mayor que $713$ .