Operazione modulo nell'algoritmo RSA.
Sto svolgendo degli ersercizi sul metodo di crittografia a chiave pubblica RSA.
Dopo aver trovato la chiave pubblica e quella privata devo codificare il messaggio usando questa formula \( C=M^{e}\ \ mod\ \ n \)
Tutto ok se ho una \(M\) e una \(e\) abbastanza piccoli.
Ad esempio \(3^{4}\ \ mod\ \ 7 \) che dà \(4\)
Ma in un esercizio che sto facendo ora devo fare \( C=(124)^{79}\ \ mod\ \ 1363 \).
Addirittura la calcolatrice non riesce a farlo e considerando che dovrei fare il calcolo a mano mi è venuto il dubbio che ci sia un modo più semplice per risolverla.
Il metodo che uso io è semplicemente elevare \(124\) per \(79\) e poi dvido per \(1363\) ma come già detto a mano è impossibile.
Dopo aver trovato la chiave pubblica e quella privata devo codificare il messaggio usando questa formula \( C=M^{e}\ \ mod\ \ n \)
Tutto ok se ho una \(M\) e una \(e\) abbastanza piccoli.
Ad esempio \(3^{4}\ \ mod\ \ 7 \) che dà \(4\)
Ma in un esercizio che sto facendo ora devo fare \( C=(124)^{79}\ \ mod\ \ 1363 \).
Addirittura la calcolatrice non riesce a farlo e considerando che dovrei fare il calcolo a mano mi è venuto il dubbio che ci sia un modo più semplice per risolverla.
Il metodo che uso io è semplicemente elevare \(124\) per \(79\) e poi dvido per \(1363\) ma come già detto a mano è impossibile.
Risposte
Tieni sempre presenti le proprietà dell'aritmetica modulare 
Dà un'occhiata qui
http://en.wikipedia.org/wiki/Exponentiation_by_squaring
Dà un'occhiata qui
http://en.wikipedia.org/wiki/Exponentiation_by_squaring
Ho visto il terzo metodo proposto in questa pagina http://en.wikipedia.org/wiki/Modular_exponentiation
E' il metodo migliore o c'è qualcosa di più efficace?
E' il metodo migliore o c'è qualcosa di più efficace?
"Stevie":
Ho visto il terzo metodo proposto ...
E' generalmente l'algoritmo più usato, se non si hanno particolari problemi di efficienza. Ed è lo stesso che ti ho segnalato.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo