[Teoria] Calcolo potenza n-esima

DragonNinja · Frequentatore del Forum Registrato: Jul 05, 2005 Messaggi: 412

Ciao a tutti... dovrei darmi un esame orale di algoritmi... una possibile domanda che il prof mi potrebbe fare è di spiegargli un algoritmo per calcolare la potenza n-esima di un numero (a quanto pare l'algoritmo è molto utilizzato negli algoritmi di crittografia a chiave pubblica)... Non mi è molto chiaro il concetto. Purtroppo nel libro che ho non è neanche spiegato in senso generalizzato ma solo nello specifico. Esattamente spiega come trattare x^25... attraverso a delle divisioni arriva al risultato che x^25 = x * x^8 * x^16 e spiega che ogni esponente della x a secondo membro è una potenza del due.

Quello che non mi è chiaro è perchè siano x^8 e x^16.

Il libro dice: "Il tutto si costruisce partendo dal mattone elementare x ed elevando di volta in volta al quadrato. Il mattone x va incluso nel risultato perchè 25 è dispari (e il suo bit meno significativo è 1); il mattone x^2 non va incluso perchè 12 (la metà intera di 25) è pari; il mattone x^4 non va incluso perchè 6 (la metà di 12) è pari; va però incluso x^8 perchè 3 (la metà di 6) è dispari, così come va incluso x^16 perchè 1 (la metà di 3) è dispari. Il calcolo è finito perchè la metà intera di 1 è 0."

Cosa succede se l'esponente fosse pari invece?
Qualcuno riesce a spiegarmelo in senso generalizzato? Se magari chiedo troppo chiedendovi spiegazioni almeno riuscite a darmi il nome dell'algoritmo così da poterlo cercare nel web?

grazie ancora

salkazzo · Inviato: Ven Set 15, 2006 5:44 pm Oggetto:

Non me ne intendo molto di programmazione, ma di matematica un pochino si.. ogni numero si può ridurre a una somma di esponenti al quadrato dal numero dispari 13 (8 4 1) ai pari 52 (32 16 4)
quindi con il numero pari arrivi comunque sempre allo 0..

Chiedo pareri anche di programmatori, però.. Smile

_________________
<div align="center"><a href="http://www.briscolachiamatamilano/maggiotorneo.htm"><img border="0" src="http://www.briscolachiamatamilano/images/banner.gif" width="298" height="58"></div>

salentinu · Ospite

Come dice salkazzo è giusto...devi scomporre il numero in potenze di due, se è dispari moltiplichi per x che sarebbe "x^1".
Infatti nel tuo caso specifico:

x^25 = x^1 * x^8 * x^16

Facile intuire il perchè, la somma degli esponenti infatti è 25!

Se ti dovesse servire:
2^0 = 1
2^1 = 2
2^3 = 4
2^4 = 8
2^5 = 16
2^6 = 32
2^7 = 64
2^8 = 128
2^9 = 256
2^10 = 512
2^11 = 1024
2^12 = 2048
etc...

ar3 · Inviato: Sab Set 16, 2006 3:13 pm Oggetto:

Credo che tu abbia sbagliato a scrivere... 2^3 non è 4, ma ovviamente 8... Hai saltato una riga Wink

DragonNinja · Inviato: Sab Set 16, 2006 4:13 pm Oggetto:

Si in pratica è come se stessi convertendo il numero in binario e prendo quelle potenze solo dove la cifra (bianria) dell'esponente è 1....

salentinu · Ospite

giusto ho sbagliato a scrivere una riga:

2^0 = 1
2^1 = 2
2^2= 4
2^3 = 8
2^4 = 16
2^5 = 32
2^6 = 64
2^7 = 128
2^8 = 256
2^9 = 512
2^10 = 1024
2^11 = 2048

Scusate...ecco la correzione...non ho ben capito se sei riuscito a comprendere il concetto...