Un efficiente algoritmo per il calcolo di $x^q$ e di $x^q (mod p)$, esponenziazione veloce

hellokitty88-dove_arrivera.jpgNel presente articolo viene illustrato un efficiente algoritmo di esponenziazione, noto nella letteratura tecnica con il seguente nome: right – to – left binary method for exponentiation. Di questo algoritmo si danno due applicazioni per ciascuna delle quali è stato realizzato un programma in linguaggio Qbasic. Pertanto come corredo al presente articolo sono disponibili per il lettore anche i due relativi Eseguibili

Prima applicazione

Questa applicazione è relativa al calcolo dell’elevazione a potenza di un numero intero, cioè del calcolo di xq con i valori sia di x che di q numeri interi positivi. Per questo tipo di applicazione si può utilizzare:

• Una aritmetica a doppia precisione disponibile nel software adoperato per cui i valori di x e di q non possono essere molto grandi; in effetti, come si può notare dagli esempi riportati più avanti, i valori numerici che superano la soglia di 1015 sono dati in virgola mobile e mostrati con mantissa ed esponente. In questa rappresentazione dei numeri vi è quindi un troncamento del risultato numerico alla 16-ma cifra; in compenso viene dato con la parte seguente l’ordine di grandezza del numero. Questo però se non viene superato il valore numerico di 21024 pari a (1.797693134862315) · 10308, in quanto oltre tale valore si andrebbe in overflow.

• Una aritmetica a precisione multipla per cui la notevole limitazione di calcolo utilizzando solo l’aritmetica a doppia precisione può essere superata, L’utilizzo di tale tipo di aritmetica permette di avere risultati di calcolo esatti per qualsiasi valore numerico non eccedente il valore di 1014000 , vale a dire per valori numerici aventi fino a 14000 cifre Si possono così gestire ed elaborare con un apposito programma numeri composti anche da diverse centinaia di cifre. Il valore limite 1014000 è imposto dalle limitazioni inerenti il software del linguaggio utilizzato (QBasic).

Seconda applicazione

Questa applicazione è dedicata al calcolo di xp (mod p) con valori interi di x, q , p sia piccoli che grandi, costituiti ognuno anche da decine o addirittura da qualche centinaio di cifre.

Le due applicazioni indicate, ma soprattutto la seconda, risultano importanti in diversi campi della teoria dei numeri, in particolare nel campo della Crittografia.

ico-pdf.pngLeggi tutto l’articolo Teodoro Cristiano, Un efficiente algoritmo per il calcolo di xp e di xq (modp), esponenziale veloce.


Programma per il calcolo di xq

Questo Programma – Eseguibile è realizzato facendo riferimento a quanto illustrato ed esposto nell’articolo: Un efficiente algoritmo per il calcolo di xq e di xq (mod p)” ed è rivolto in particolare al calcolo del valore esatto di x elevato alla q-esima potenza, cioè di xq con x e q numeri interi positivi. Per svolgere i calcoli nel modo più valido viene utilizzato l’algoritmo noto con il nome di “the Right to Left Binary Algorithm”che risulta essere uno dei più efficienti metodi di esponenziazione. Poiché nel calcolo di xq si devono effettuare operazioni aritmetiche in modo esatto su numeri interi formati anche da centinaia di cifre, si utilizza una aritmetica a precisione multipla. Date le limitazioni insite nel software del linguaggio utilizzato, con il presente Eseguibile non si possono ottenere per xq valori formati da un numero di cifre superiore a 14000. Pertanto si può calcolare in modo esatto un qualsiasi valore numerico di xq non eccedente il valore di 1014000.Viene qui infine data l’informazione che l’eseguibile offre due opzioni per la presentazione del numero xq; opzioni che vengono illustrate chiaramente sullo schermo prima dell’inizio dei calcoli.

ico-zip.pngEseguibile Algoritmo X^QALTO


Programma per il calcolo di xq modp

Il presente Programma-Eseguibile è realizzato facendo riferimento a quanto illustrato ed esposto nel seguente l’articolo: Un efficiente algoritmo per il calcolo di xq e di xq (mod p)” Il Programma-Eseguibile è rivolto al calcolo del valore esatto di xq (mod p ) vale a dire del resto o residuo della divisione per il numero intero p di x elevato alla q-esima potenza, con x, q e p numeri interi positivi. Per svolgere i calcoli nel modo più efficiente viene utilizzato l’algoritmo noto come “the Right to Left Binary Algorithm” che è uno dei più validi metodi di esponenziazione. Poiché nel calcolo di xq (mod p) si devono effettuare operazioni aritmetiche in modo esatto su numeri interi formati anche da varie centinaia di cifre, si è utilizzata una aritmetica a precisione multipla. L’utilizzazione del presente Eseguibile risulta essenziale per il calcolo in modo esatto e veloce di xq (mod p) in vista delle sue importanti applicazioni nel campo della crittografia.

ico-zip.pngEseguibile Algoritmo X^QMODP

Commenti

commenti