Le riduzioni dell'esponente - i conti della serva

Abbiamo visto nei due blog precedenti il Piccolo Teorema di Fermat (PTF) e la generalizzazione di Eulero,
che qui riassumiamo brevemente:

a^n-1 mod n = 1 mod n (1)

a^phi(n) mod n = 1 mod n (2)

dove phi(n) è la funzione totiente di Eulero. Se p=n phi(n) = p-1 e la (2) e la (1) sono equivalenti. La funzione totiente phi(n) è l'insieme di numeri minori di n coprimi con n. Ad esempio phi(8) = 4, perchè i numeri minori di 8 e coprimi con esso sono: 1,3,5,7. Se n è un numero primo ad esempio phi(7) = 6; infatti coprimi con 7 sono: 1,2,3,4,5,6.

La cosa funziona sia con a e n coprimi che non. Se non sono coprimi, si parla di pseudo-primalità di n
rispetto alla base a.

Questo torna utile in vari tipi di problemi. Ad esempio se volessimo sapere qual è l'ultima cifra di 7^222?
Oppure ridurre l'esponente nel calcolo del modulo? Qua è importante che a e n siano coprimi.

Ora 7^222 mod 10 hanno 7 e 10 coprimi e phi(10)=4 {1,3,7,9}.
Dalla (2) allora è 7^4 mod 10 = 1 mod 10 (3).

Per cui tenendo conto della (3)
7^222 mod 10 = 7^4*55+2 mod 10 = 7^(4*55) * 7^2 mod 10 = 1^55 * 7^2 mod 10 = 9 mod 10

Questa tecnica funziona se a ed n sono coprimi e si ottiene elevando la base a al valore phi(n); difatti
se x = y mod phi(n) allora a^x = a^y mod n. Inoltre è quella più "rapida".

Cosa si risparmia? Facciamo il binary(x)

? binary(222)
%1 = [1, 1, 0, 1, 1, 1, 1, 0]
? binary(2)
%2 = [1, 0]

Si risparmia molto, ma è un metodo lento per il test di primalità; adesso vediamo perchè.

Prima beffa
Nel caso di 2^240 mod 241 = 1 mod 241 possiamo fare phi(241)=240 [qua già sappiamo che 241 è primo],
il problema è di avere una eulerphi() che deve fare il MCD (algoritmo di Euclide) di tutti i numeri tra 1 e 241, contando quelli che hanno MCD(x,241)=1. Se il numero è molto più grande di 241, il metodo è lento e richiede, tra l'altro, una pre-elaborazione per la riduzione.

Seconda beffa
Nella primalità quanto si risparmia in bit? nulla : 2^240 mod 241 = 2^240*1 mod 241.

Un'altra idea
L'idea allora è quella di ridurre l'esponente dividendolo per un divisore e trasformare il test:

a^n-1 mod n = 1 mod n

La relazione di sopra comporta che se n è il numero dispari sotto test, n-1 è un pari sicuramente divisibile per 2 ... Per grossi valori di n  (n-1)/2 è intero; allora nel caso precedente avremo 2^120 mod 241. Ma  quanto abbiamo risparmiato? Facciamo anche qui il binary(x)

? binary(240)
%9 = [1, 1, 1, 1, 0, 0, 0, 0]
? binary(120)
%10 = [1, 1, 1, 1, 0, 0, 0]

Si risparmia un solo bit!! Poco se vogliamo. Conviene quasi di lasciar fare al ModExp col numero integro.
La discussione dimostra in modo semplice, senza tirar fuori la teoria della complessità che la velocità non si ottiene dalla riduzione dell'esponente ma dal numero di step necessari all'operazione modulo. Inoltre il test di primalità se vuole diventare più veloce necessita di ridurre molto il numero di basi di prova. 

Alla prox.