Categorie
Linux

Metodo Delle Quadrature Successive con Esempio

Introduciamo ora il Metodo Delle Quadrature Successive (con Esempio) e vediamo come trovare il valore di 6^79 (mod 91) in 3 semplici passaggi:
  1. Scomporre l’esponente come somma di potenze di due (nell’esempio 79 = 64 + 8 + 4 + 2 + 1).
  2. Calcolare il valore della base elevata a tutti gli esponenti di due, ovviamente in modulo, partendo da 0 fino al massimo trovato. (Nel nostro esempio 6^2 (mod 91), 6^4 (mod 91), …, 6^32 (mod 91), 6^64 (mod 91) ricordandoci che possiamo sfruttare i risultati precedenti, ad esempio 6^2 (mod 91) = 36, 6^4 (mod 91) = 36^2 (mod 91).
  3. Concentriamoci adesso sui soli risultati che ci interessano, moltiplicandoli. (nel nostro esempio 6^2, 6^4, 6^8, 6^64 (6^0 e 6^1 li ottieni banalmente) tutti modulo 91.

A questo punto sia x il prodotto del punto 3, si calcola x mod 91 = y. Con quest’ultimo come risultato finale.

L’incremento di efficienza rispetto al prodotto iterato si vede anche ad occhio