Teoria degli indici

[Piccolo Fermat]

Dalla teoria sono riuscito a capire che

$IND_r(a)= h$ dove $h$ non è che $r^h -= a (mod n)$

quindi se ho una radice primitiva $r=5$ e $a=11$ $n=18$ avrò

$IND_5(11)= h$ dove $h$ è $5^h -= 11 (mod 18)$

chi mi spiega un metodo più intuitivo per trovare questa benedetta $h$?

[Lord K]

Tempo fa creai un topic su questo forum con il titolo Logaritmo discreto che ora non riesco a linkarti e che non trovo. In ogni caso l'idea è piuttosto semplice da seguire, solo che hai bisogno del simbolo di Legendre o di Jacobi.

In particolare si suppone che [tex]h[/tex] sia pari, ma se lo fosse allora [tex]h=2\cdot h_0[/tex] ovvero che sia:

[tex]5^{2h_0}=11(18)[/tex]

ma qui implica che valga [tex]1[/tex] il simbolo [tex]\displaystyle(\frac{11}{18})[/tex]. Qui abbiamo, mediante Jacobi che [tex]\displaystyle(\frac{11}{18})=(\frac{11}{2})(\frac{11}{2=-1[/tex] non è un residuo quadratico modulo [tex]18[/tex], quindi [tex]h[/tex] è dispari.

Da qui ripetiamo [tex]h=2\cdot h_1+1[/tex]

[tex]5^{2h_1+1}=11(18)[/tex]
[tex]5\cdot 5^{2h_1}=11(18)[/tex]

L'inverso di [tex]5[/tex] è [tex]-7[/tex] visto che [tex]gcd(18,5)=1[/tex] e che [tex]2\cdot 18 - 7 \cdot 5=1[/tex], allora:

[tex]5\cdot 5^{2h_1}=11(18)[/tex]
[tex]5^{2h_1}=13(18)[/tex]

E qui ripeto il ragionamento precedente. Praticamente la scelta di questi [tex]h_i[/tex] fa in modo che ci sia una successione di numeri naturali decrescenti che ha un numero finito di passi prima di concludere che non c'è una soluzione o trovandola.