Aritmetica modulare

[HolyFather]

Qualcuno sa come eseguire questo calcolo

98^(7253) (mod 143)

senza eseguire brutalmente l'esponenziale 98^7253 ??

grazie !

[fred84]

http://www.wolframalpha.com/input/?i...253%29+mod+143

[HolyFather]

Originariamente inviato da fred84
http://www.wolframalpha.com/input/?i...253%29+mod+143

bello sto link lo ho messo nei preferiti

però volevo anche sapere se c'era un modo per risolverlo a manina

[bubi1]

Purtroppo 7253 e' primo, quindi non puoi ridurre nulla. Altrimenti avresti potuto utilizzare il teorema di euler, la funzione di carmichael, etc.

Di conseguenza ti tocca fare un po' di esponenziazione modulare.

partiamo dal risultato=1, base=98.
dividiamo l'esponente a 2 fino ad arrivare a 0; prendiamo il valore assoluto del risultato
ad ogni passo facciamo che base=base^2 mod 143
ad ogni passo con un valore dispari facciamo che risultato = risultato*base mod 143

quindi abbiamo

7253
risultato = 1*98 mod 143 = 98
base = 98^2 mod 143 = 23
3626
base = 23^2 mod 143 = 100
1813
risultato = 98*100 mod 143 = 76
base = 100^2 mod 143 = 133
906
base = 133^2 mod 143 = 100
453
risultato = 76*100 mod 143 = 21
base = 100^2 mod 143 = 133
226
base = 133^2 mod 143 = 100
113
risultato = 21*100 mod 143 = 98
base = 100^2 mod 143 = 133
56
base = 133^2 mod 143 = 100
28
base = 100^2 mod 143 = 133
14
base = 133^2 mod 143 = 100
7
risultato = 98*100 mod 143 = 76
base = 100^2 mod 143 = 133
3
risultato = 76*133 mod 143 = 98
base = base = 133^2 mod 143 = 100
1
risultato = 98*100 mod 143 = 76

in c tutto questo dovrebbe essere piu' o meno cosi':

int mod_pow(int base, int exp, int mod){
        int result = 1;
        while (exp>0){
                if (exp & 1 == 1)
                        result = result * base % mod;
                exp = exp >> 1;
                base = base * base % mod;
        }
        return result;
}

[quaestio]

giuro che mi fate paura.

[albgen]

per gli interessati diamo anche la versione C#

        private static int mod_pow(int labase, int exp, int mod)
        {
            int result = 1;
            while (exp > 0)
            {
                if ((exp & 1) > 0)
                    result = result * labase % mod;
                exp = exp >> 1;
                labase = labase * labase % mod;
            }
            return result;
        }

mod_pow(98, 7253, 143);//risultato 71

[fred84]

Originariamente inviato da albgen
risultato 71

che è sbagliato

[albgen]

Originariamente inviato da fred84
che è sbagliato

ho sbagliato a scrivere...è 76 e ovviamente l'agoritmo è corretto.

[HolyFather]

grazie raga

[vortex87]

Originariamente inviato da bubi1
in c tutto questo dovrebbe essere piu' o meno cosi':

int mod_pow(int base, int exp, int mod){
        int result = 1;
        while (exp>0){
                if (exp & 1 == 1)
                        result = result * base % mod;
                exp = exp >> 1;
                base = base * base % mod;
        }
        return result;
}

Originariamente inviato da albgen
per gli interessati diamo anche la versione C#

        private static int mod_pow(int labase, int exp, int mod)
        {
            int result = 1;
            while (exp > 0)
            {
                if ((exp & 1) > 0)
                    result = result * labase % mod;
                exp = exp >> 1;
                labase = labase * labase % mod;
            }
            return result;
        }

Beh, in effetti è decisamente diverso.