Qualcuno sa come eseguire questo calcolo
98^(7253) (mod 143)
senza eseguire brutalmente l'esponenziale 98^7253 ??
grazie !
Qualcuno sa come eseguire questo calcolo
98^(7253) (mod 143)
senza eseguire brutalmente l'esponenziale 98^7253 ??
grazie !
bello sto link lo ho messo nei preferitiOriginariamente inviato da fred84
http://www.wolframalpha.com/input/?i...253%29+mod+143
però volevo anche sapere se c'era un modo per risolverlo a manina
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':
codice: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; }
giuro che mi fate paura.
"ci vorrebbero anche più persone come quaestio (a reb verrà un brivido)" wallrider, 22/10/2012
"Se hai una vita di merda facebook non può essere molto meglio...". kalosjo, 16/10/2012
per gli interessati diamo anche la versione C#
mod_pow(98, 7253, 143);//risultato 71codice: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; }
I got the remedy
che è sbagliatoOriginariamente inviato da albgen
risultato 71
ho sbagliato a scrivere...è 76 e ovviamente l'agoritmo è corretto.Originariamente inviato da fred84
che è sbagliato
I got the remedy
grazie raga
Originariamente inviato da bubi1
in c tutto questo dovrebbe essere piu' o meno cosi':
codice: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; }
Beh, in effetti è decisamente diverso.Originariamente inviato da albgen
per gli interessati diamo anche la versione C#
codice: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; }