Matematica e crittologia - Aritmetiche finite - Il teorema cinese del resto
Prodotto modulare con il teorema cinese del resto
Aritmetiche finite - Algoritmo euclideo

Mostriamo con una pagina PhP come un prodotto modulo pq (p e q sono primi) possa essere ridotto a due prodotti modulo p e modulo q con l'aiuto del teorema cinese del resto.

Il calcolo viene eseguito in due modi: 1) calcolano il prodotto ab e quindi il modulo pq; 2) calcolando i due prodotti ab mod p e ab mod q e quindi il numero x previsto dal teorema cinese del resto. I due risultati vengono riportati e sono sempre uguali.

Viene anche calcolato il tempo di esecuzione misurato in microsecondi dalle varie procedure. Risulta evidente che il tempo di calcolo in modulo p o q è nettamente inferiore a quello in modulo pq. Va osservato che mentre per l'operazione di modulo viene impiegato l'operatore % che è precompilato in PhP, per il calcolo dell'algortimo euclideo viene impiegata una mia funzione PhP che viene interpretata dal server (cioè tradotta da PhP in linguaggio macchina istruzione per istruzione) con tempo di esecuzione inevitabilmente molto superiore. Questo spiega perché con il secondo metodo si ottengano tempi totali spesso superiori, tanto più quanto a e b sono grandi, rispetto al primo. Con una funzione "algoritmo euclideo" precompilata i tempi dovrebbero essere nettamente inferiori.

Questo metodo viene a volte usato nelle implementazioni del cifrario RSA per velocizzare il calcolo del prodotto in modulo pq che è poi la chiave pubblica di RSA.

Numeri primi p = q = Fattori del prodotto a = b =

Fonti bibliografiche e collegamenti