ab = x mod n
b = loga x mod n
| in base 2 | in base 3 | in base 4 | in base 5 | in base 6 |
|---|---|---|---|---|
| 20 = 1 | 30 = 1 | 40 = 1 | 50 = 1 | 60 = 1 |
| 21 = 2 | 31 = 3 | 41 = 4 | 51 = 5 | 61 = 6 |
| 22 = 4 | 32 = 2 | 42 = 2 | 52 = 4 | 62 = 1 |
| 23 = 1 | 33 = 6 | 43 = 1 | 53 = 6 | 63 = 6 |
| 24 = 2 | 34 = 4 | 44 = 4 | 54 = 2 | 64 = 1 |
| 25 = 4 | 35 = 5 | 45 = 2 | 55 = 3 | 65 = 6 |
| 26 = 1 | 36 = 1 | 46 = 1 | 56 = 1 | 66 = 1 |
e quindi p.es. il log24 è 2 ma anche 5. Viceversa non esistono log23, log25, log26. Situazione simile per le potenze in base 4 e in base 6.
In base 3 (che è un generatore modulo 7) esiste il logaritmo di tutti i numeri tra 1 e 6, e, se si esclude lo 0, l´operazione è univoca: p.es. log36 = 3; log32 = 2 ... Situazione simile per le potenze in base 5, che è a sua volta un generatore.
Si nota poi che la potenza con esponente N - 1 = 6 vale sempre 1, come vuole il piccolo teorema di Fermat.
Per N piccolo come in questo caso il calcolo del logaritmo si può fare con una semplice ricerca esaustiva sulla tabella sopra; ma per N molto grande, con decine o centinaia di cifre decimali, questo metodo diventa estremamente lento. E fino ad oggi non si sono trovati metodi molto più efficienti di questo. In generale si ritiene che la complessità computazionale del calcolo del logaritmo discreto sia dello stesso ordine di una fattorizzazione anche se manca una dimostrazione.
Questo sito non fa uso di cookies propri. Possono peraltro essere presenti cookies di terze parti.
Pagina a cura di Paolo Bonavoglia (paolo@bonavoglia.eu) del