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

Teodoro Cristiano 1

teodorocristiano@tiscali.it q q

x x

Un efficiente algoritmo per il calcolo di e di (mod p)

( Esponenziazione veloce)

Introduzione

Nel presente articolo viene illustrato un efficiente algoritmo di esponenziazione, noto nella letteratura tecnica

right - to - left binary method for exponentiation.

con il seguente nome: due applicazioni

Di questo algoritmo si danno 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

q

x con i valori sia di che di numeri interi positivi. Per questo tipo di applicazione si può utilizzare:

x q

Una disponibile nel software adoperato per cui i valori di e di

aritmetica a doppia precisione x q

• non possono essere molto grandi; in effetti, come si può notare dagli esempi riportati più avanti,

15

i valori numerici che superano la soglia di sono dati in virgola mobile e mostrati con mantissa ed

10

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.

1024 308

2 pari a (1.797693134862315) , in

Questo però se non viene superato il valore numerico di 10

·

quanto oltre tale valore si andrebbe in overflow.

Una per cui la notevole limitazione di calcolo utilizzando solo

aritmetica a precisione multipla

• l’aritmetica a doppia precisione può essere superata, L’utilizzo di tale tipo di aritmetica permette di

14000

avere risultati di calcolo esatti per qualsiasi valore numerico non eccedente il valore di , vale a

10

dire per valori numerici aventi fino a 14000 cifre Si possono così gestire ed elaborare con un apposito

14000 è imposto dalle

programma numeri composti anche da diverse centinaia di cifre. Il valore limite 10

limitazioni inerenti il software del linguaggio utilizzato (QBasic).

Seconda applicazione q

x (mod p)

Questa applicazione è dedicata al calcolo di con valori interi di sia piccoli che grandi,

x, q , p

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

campo della Crittografia.

numeri, in particolare nel

q

x

CALCOLO di

prima applicazione

Riguardo alla viene illustrato in dettaglio l’algoritmo in questione in quanto esso sarà

utilizzato anche nell’altra applicazione. I principali passi che si devono fare riguardo al calcolo della

q

x

elevazione a potenza di un numero, cioè del calcolo di con valori di e di numeri interi positivi,

x q

sono elencati qui di seguito:

1) introdurre la variabile x 2

2) introdurre la variabile q

3) calcolare il valore di espresso in cifre binarie e memorizzarlo in un vettore;

q

si abbia ad esempio il seguente valore binario per : 110101101 e si indichi con = 8 il numero di

q n

cifre binarie che compongono ; dette cifre verranno memorizzato nel vettore a(j)

q

con j = 0, 1, 2, 3, 4, 5, 6, 7, 8 :

a(8)=1, a(7)=1, a(6)=0, a(5)=1, a(4)=0, a(3) = 1, a(2)=1, a(1)=0, a(0)=1

4) introdurre la variabile e porre :

c

= 1 se è pari , cioè se a(0) 0

c q =

se è dispari, cioè se a(0) 1

c = x q =

5) formare il seguente ciclo iterativo:

per ogni valore di j da 1 ad si effettuino nell’ordine le seguenti operazioni:

n-1

inizio ciclo

porre z = x x

·

se a( j ) è di valore 1 porre e quindi

y = z c c = y

·

porre x = z

tornare all’inizio del ciclo q

x

6) terminato tale ciclo di operazioni l’ultimo valore che si ottiene ottenuto per è il valore di

c

Facciamo un semplice esempio: 34

x

si voglia trovare il valore di

Eseguendo le operazioni indicate nei passi indicati sopra si ha:

q 34,che espresso in cifre binarie ha il seguente valore: q 1 0 0 0 1 0

= =

essendo q = 34 numero pari e quindi a(0) = 0 si pone = 1

c j, a(j), z, y, c,

eseguendo il ciclo per j da 1 sino ad n-1 e visualizzando opportunamente le variabili ha

si

la seguente tabella:

j a(j) z y = z c c = y

·

2 2 2

1 1 1

·

x x x

4

2 0 x 8

3 0 x 16

4 0 x 34

32 32 2

5 1 x

·

x x x

Come si nota l’ultimo valore ottenuto per è proprio il valore cercato

c

Un esempio numerico chiarirà ancora di più l’algoritmo.

34

Si voglia calcolare il valore di 7

34 in cifre binarie ha il seguente valore: q 1 0 0 0 1 0

=

essendo 34 un numero pari e quindi a(0) = 0 e si pone = 1

c j, a(j), z, y, c

eseguendo il ciclo per j da 1 sino ad e visualizzando opportunamente le variabili ha

n-1 si

la seguente tabella di valori numerici: 3

j a(j) z y = z c c = y

·

2 2 2

1 1 7 7 = = 49 1 49 = 49

7 7 7

· · =

2 2 4

2 0 = = 2401

7 7 7

·

4 4 8

3 0 = = 5764801

7 7 7

·

8 8 16

4 0 = = 33232930569601

7 7 7

·

16 16 32 27 32 2 34 34 28

5 1 = = 1.104427674243921 = = 5.411695603795212

7 7 7 10 7 7 7 7 10

· · · ·

15

Come si vede i valori numerici maggiori di sono espressi in virgola mobile e mostrati con mantissa ed

10

esponente. programma relativo al

Diamo qui ora in un linguaggio evoluto, ad esempio in linguaggio Qbasic, un

q

x

calcolo di relativo alla prima applicazione, limitatamente cioè all’impiego della sola aritmetica a doppia

precisione ' Programma "X^Q.BAS" (programma con illustrazione didattica)

' Il programma Š relativo a determinare il valore di x^q con l'algoritmo di

' esponenziazione noto come "THE RIGHT TO LEFT BINARY ALGORITHM"

' i valori numeri di x e q non devono essere eccesivamente grandi per

' non eccedere nei risulti il valore massimo di 10^308

CLS : PRINT : PRINT "CALCOLO di x^q ": DEFDBL A-Z

INPUT "x"; x: INPUT "q"; q

t1 = TIMER

REM q viene espresso ora in forma binaria

ww = LOG(q) / LOG(2): n = INT(ww)+1: PRINT "n="; n

DIM a(n)

w = q: PRINT " q espresso in binario :";

FOR j = 0 TO n-1: d = INT(w / 2): a(j) = w - 2 * d: w = d: NEXT j

FOR j = n-1 TO 0 STEP -1: PRINT a(j); : NEXT j

REM si effettua ora con le istruzioni sotto riportate l'operazione x^q

b = x: c = x: IF a(0) = 0 THEN c = 1

PRINT : PRINT "q ="; q, "b ="; b, : PRINT "y ="; c

PRINT : PRINT " j "; " a(j)", " z "; SPC(26); "y"

s = 0: PRINT

'DO: y$ = INKEY$: LOOP WHILE y$ = ""

REM inizio ciclo

FOR j = 1 TO n-1: PRINT j; " "; a(j),

z = b * b: PRINT z,

IF a(j) = 1 THEN y = c * z: c = y:

IF a(j) = 1 AND y < 10 ^ 18 THEN s = 14: PRINT SPC(s); y

IF a(j) = 1 AND y > 10 ^ 18 THEN s = 0: PRINT SPC(s); y

b = z

PRINT

NEXT j

Rem fine ciclo

PRINT : PRINT " x ^ q = y ="; y

PRINT : PRINT "CALCOLO DIRETTO DI"; x; "^"; q

PRINT x; "^"; q ; "="; x ^ q

REM fine operazione: e'stato trovato il valore numerico di x^q

PRINT : PRINT "tempo di calcolo ="; TIMER - t1; "secondi"

PRINT "numero di iterazioni:"; j - 1

END 4

143

In relazione all’utilizzo di detto programma si mostra l’esempio di calcolo di che è un numero di 69

3

cifre.

Eseguendo il programma si otterrà sullo schermo del monitor il seguente risultato:

(1° esempio)

x ? 3

q? 143

q espresso in binario : 1 0 0 0 1 1 1 1

x = 3 c = x y = 3

j a(j) z y = z*c

1 1 9 27

2 1 81 2187

3 1 6561 14348907

4 0 43046721

5 0 1853020188851841

6 0 3.433683820292512D+30

7 1 1.179018457773858D+61 1.691762620188052D+68

y = 3 ^ 143 = 1.691762620188052D+68

numero di iterazioni : 7

tempo di calcolo = 0 secondi 15

Si ribadisce che i valori numerici che superano la soglia di sono dati in virgola mobile e mostrati con

10

mantissa ed esponente in quanto è stata utilizzata nei calcoli solo la doppia precisione.

q

x q

CALCOLO di con valori di e grandi

x

q

x

Per poter calcolare con esattezza con valori grandi di e è stato realizzato un ulteriore programma

x q

nel quale viene utilizzata un’ aritmetica a precisione multipla. Per tale programma, di cui in questo articolo

non viene dato il listato, occorre specificare quanto segue:

Se per valori non grandi di e le variabili in gioco ( vedi x ,q, b, c, z, y) si possono trattare come semplici

x q

numeri, ora invece ognuno di questi numeri, che potrebbe essere costituito anche da centinaia di cifre, per

poter essere inserito ed elaborato nella sua interezza, deve essere preso in considerazione come stringa

alfanumerica da memorizzare poi in un adeguato vettore, nelle cui celle vengono inserite in modo opportuno

tutte le cifre del numero stesso. Le operazioni aritmetiche sui diversi vettori saranno poi effettuate con le

modalità indicate nell’articolo citato in [CT] . q

x

Date tuttavia anche qui le limitazioni inerenti al software del linguaggio Qbasic utilizzato il valore di

14000

non deve superare il valore numerico di , vale a dire non si possono avere valori numerici costituiti da

10

più di 15000 cifre.

Qui di seguito viene dato un 2° esempio di calcolo con gli stessi valori d i x e q del 1° esempio con il

risultato ottenuto utilizzando l’aritmetica a precisione multipla.

------------------------

[CT] : Cristiano Teodoro – “ sul calcolo della radice quadrata intera di un numero grande”

Matematicamente.it – Approfondimenti – Matematica 5

2° ESEMPIO

--------------------------------------------------- CALCOLO di x^q ----------------------------------------------------

INTRODUCI IL NUMERO x E POI BATTI TASTO Invio : 3

INTRODUCI L'ESPONENTE q E POI BATTI TASTO Invio : 143

-- ----------------------------------------------------------------------------------------------------------------------------

3 ^ 143 = 169176 2620188 0520023 9918053 2472321 1896958 0750063 8879624 2120914 7371627

cifre di 3 ^ 143 : 69

tempo effettivo di calcolo: 0 secondi

nel seguente esempio il calcolo risulta un po’ più elaborato ottenendo però tempi di esecuzione molto brevi

321

678

3° ESEMPIO : calcolo di

---------------------------------------------- CALCOLO di x^q ----------