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
Algoritmo calcolo potenza n-esima
-
MdF
Molto a occhio, mi pare che si possa fare analogia col codice binario. In esso, $ $ 25_d = 0001|1001_b $ $.
$ $ 25_d = {(16+8+1)}_d $ $
$ $ 0001|1001_b = {(2^4+2^3+2^0)}_d={(16+8+1)}_d $ $
Quindi, se così fosse, si tratta semplicemente di scomporre in binario l'esponente avuto inizialmente (nel caso visto è 25) e avere tanti fattori quanti sono le cifre a 1: questi fattori hanno come esponente quello corrispondente al peso.
Es. $ $ x^{30} = x^{16} \cdot x^8 \cdot x^4 \cdot x^2 $ $
perché $ $ 30_d = 0001|1111_b = {(2^4+2^3+2^2+2^1)}_d={(16+8+4+2)}_d $ $.
$ $ 25_d = {(16+8+1)}_d $ $
$ $ 0001|1001_b = {(2^4+2^3+2^0)}_d={(16+8+1)}_d $ $
Quindi, se così fosse, si tratta semplicemente di scomporre in binario l'esponente avuto inizialmente (nel caso visto è 25) e avere tanti fattori quanti sono le cifre a 1: questi fattori hanno come esponente quello corrispondente al peso.
Es. $ $ x^{30} = x^{16} \cdot x^8 \cdot x^4 \cdot x^2 $ $
perché $ $ 30_d = 0001|1111_b = {(2^4+2^3+2^2+2^1)}_d={(16+8+4+2)}_d $ $.