Algoritmo calcolo potenza n-esima
Inviato: 15 set 2006, 16:20
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
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