-
Stiamo cercando una procedura numerica che è facile in una direzione,
-
ma difficile nel senso inverso.
-
Questo ci porta all'aritmetica modulare, a volte detta aritmetica dell'orologio.
-
Per esempio, per calcolare 46 mod 12, possiamo prendere una fune lunga 46 unità,
-
e avvolgerla attorno ad un orologio di 12 unità, chiamato modulo.
-
La soluzione si trova dove finisce la fune.
-
Per cui diciamo che 46 mod 12 è congruente a 10.
-
Facile. Adesso, affinché funzioni, usiamo un modulo primo, come 17,
-
e troviamo una radice primitiva di 17, in questo caso 3.
-
Che ha l'importante proprietà che quando viene elevata a esponenti diversi,
-
la soluzione si distribuisce uniformemente attorno all'orologio.
-
3 viene chiamato generatore. Se eleviamo 3 a qualsiasi esponente x,
-
ogni numero intero fra 0 e 17 ha la stessa probabilità di essere la soluzione.
-
La procedura inversa è però difficile.
-
Per esempio, se ci viene dato 12, e dobbiamo trovare l'esponente a cui 3 deve venir elevato,
-
questo problema si chiama il problema del logaritmo discreto.
-
E adesso abbiamo la nostra funzione a senso unico.
-
Facile da eseguire, ma difficile da invertire.
-
Dato il numero 12, dovremmo provare a caso per trovare l'esponente giusto.
-
Ma quanto è difficile?
-
Con numeri piccoli è facile, ma se usiamo un modulo primo lungo centinaia di cifre
-
diventa pressoché impossibile da risolvere.
-
Anche avendo accesso a tutta la potenza di calcolo del mondo, sarebbero necessari migliaia di anni
-
per provare tutte le possibilità.
-
Quindi la forza di una funzione a senso unico si basa sul tempo necessario per invertirla.
