Alice, Bob e Eva — modpow

“Senti, ma secondo te era facile decrittare quel codice che mi hai dato da studiare?”.

“Eh, no”.

“E poi, con dei numeri così, come si fa anche solo a calcolare la potenza e il modulo? Sono numeri giganteschi”.

“Quello non è un problema, si fa in un attimo con qualunque linguaggio. Vanno benissimo anche i linguaggi ad alto livello, che supportano gli interi a qualunque precisione. Anche se sono linguaggi interpretati, non c'è problema”.

“Davvero?”.

“Sì, guarda, ti faccio vedere una funzione pyhton che fa il calcolo rapidamente”.

def modpow(c,d,n):
  m=1
  while d >= 1:
    if d & 1:
      m=c*m % n
    c=c*c % n
    d = d >> 1
  return m

“Mh, non capisco mica bene”.

“Eh, perché è stato scritto tenendo presente le proprietà della notazione binaria, ma potrebbe essere scritto anche in maniera più chiara”.

“E non potevi scriverlo in maniera più chiara subito?”.

“Certo che no, è come quando i medici scrivono le diagnosi o le ricette. Meno gente capisce, più si sentono superiori”.

“Andiamo avanti, per piacere”.

“Ok, ok. Comunque la notazione che ho usato è anche didattica, eh”.

“Eh, va bene, sentiamo la scusa”.

“Per esempio, la riga if d & 1 si domanda se d AND 1 è vera, cioè se d, scritto in binario, finisce con 1, cioè se d è congruente a 1 modulo 2. È un modo rapido per controllare se d è dispari”.

“Ah, bello”.

“E la riga che trasforma d in d>>1 sta a significare che i bit di d vengono tutti spostati di uno verso destra. In pratica è la divisione di d per 2, gettando via il resto”.

“E questa serie di operazioni è proprio la potenza c^d mod n?”.

“Sì. Funziona in questo modo: si prende l'esponente d in forma binaria e lo si esamina una cifra alla volta, a partire dal fondo. Se c'è una cifra zero, significa che l'esponente è pari. Allora faccio il quadrato di c e divido l'esponente 2. Se invece c'è una cifra uno, l'esponente è dispari. Allora, prima moltiplico m per c, e poi faccio come prima. Poi getto via l'ultima cifra binaria di d e ricomincio. Ecco le formule:”.

c^d = (c²)^d/2, se d è pari;
c^d = c(c²)^d/2, se d è dispari (e d/2 è la divisione in cui getto via il resto).

“Ah, e quindi non devo fare un'infinità di moltiplicazioni”.

“Eh, no, devi fare tante operazioni quante sono le cifre binarie di d: questo algoritmo ha quindi bisogno di un numero di operazioni proporzionale al logaritmo in base 2 di d. In questo caso il ciclo viene eseguito solo 426 volte”.

“Sembra quasi miracoloso”.

“Ora che hai capito, ti scrivo la funzione in maniera più comprensibile:”.

def modpow(c,d,n):
  m=1
  while d>=1:
    if d % 2 == 1:
      m=c*m % n
    c=c*c % n
    d = d/2 
  return m

“Ah, grazie, serve a molto adesso… Comunque, rimane il problema di fattorizzare quell'n enorme. Da quanto ho capito fino ad ora, non esiste un modo veloce per farlo”.

“Eh, no. La storia di come è stato fattorizzato n la raccontiamo la prossima volta”.

⇐ · ⇒