qui partiamo con la fine dell’aritmetica modulare. vedremo come il teorema cinese dei resti e’ un risultato che serve per rendere piu’ efficiente l’esecuzione di algoritmi come RSA che ha numeri davvero grandi.
Sotto opportune ipotsei:
esiste l’inverso di un elemento. A volte abbiamo pero’ a che fare con moduli che non sono primi ma numeri che sono prodotti di numeri primi.
Supponiamo di dover fare questo conto 324 * 1137 * (1222 -861+56)mod1265
come possiamo fare? se il modulo non e’ primo e posso conoscere la fattorizzazione, come posso fare? (RSA siamo in prodotto tra due primi quindi la sappiamo). Possiamo calcolare questa espressione n = 1265, n =5 x 11 x 23
facciamo i conti rispetto al modulo dei primi componenti, e ottengo praticamente tre numeri, possiamo pero’ ritornare pero’ al risultato del modulo di 1265 e come? come facciamo a fare questo mapping da Z_1265. Faccio i conti in Z_5,11,23 e poi posso tornare indietro in maniera biiettiva. Come faccio a farlo?
usando i moduli ottengo come resti: 1 2 14. come faccio a tornare indietro a questo punto? se abbiamo operazioni di costo quadratico, se un numero grosso non sta in macchina lo devo andare a simulare via software quindi se ho due numeri di n bit il mio costo e’ n^2, non ho algoritmi piu’ veloci o comunque non lineari.
alla fine pero’ mi costa meno andare avanti e andare indietro che andare a calcolare direttamente sul prodotto composto, quindi conviene fare cose con moduli piccoli e mettere insieme.
questo ha senso quando i numeri non stanno in macchina, perche’ se ci sto posso andare a usare la circuiteria. Come facciamo a tornare indietro?
devo trovare dei coefficienti tali per cui C + c1a1 + c2a2 + c3a3
tale per cui Cmodqi = ai
e alla fine potremmo concludere che alla fine C = a
Pariamo da calcolare mi
usando gli inversi modulari posso andare a calcolare i ci:
