Aritmetica modulare

[edoclimb]

Ciao, nell'ambito della crittografia RSA devo calcolare: cexp(d) (mod N). Il problema è che c alla d può essere un numero veramente grande, difficile da calcolare mentre il (mod N) è sicuramente minore di N.
La mia domanda è: esiste un modo di calcolare l'espressione scritta sopra senza dover calcolare il valore c alla d? Cioè, posso frazionare il calcolo della potenza calcolando dei (mod N) parziali per poi arrivare al risultato finale?

Grazie della disponibilità.

[Tipper]

Se ho capito bene la domanda, puoi usare il metodo dei quadrati ripetuti.

[Lord K]

Io non ne so molto di RSA, ma se devi calcolare:

$c^d(N)$

Il modo migliore per procedere potrebbe essere:

1) Calcolare $phi(N)$
2) Trovare $d_0-=d(phi(N))$
3) Trovare $c_0-=c(N)$

e quindi osservare che:

$c^d-=c_0^(d_0)(N)$

[edoclimb]

Grazie, in realtà il metodo dei quadrati ripetuti è quallo che cercavo. Permette di semplificare enormemente il calcolo di potenze. Qui sotto un link con unesempietto molot semplice.

Grazie.
http://www.genews.net/giornalino_06_07/ ... _resto.swf