Logaritmo discreto

[Lord K]

Sia $a,b,c in ZZ$, vogliamo calcolare $x$ tale che:

$a^x-=b mod c$

scritto anche come:

$a^x-=b(c)$

[Lord K]

Visto che non ci provate, vi propongo la mia idea:

Per semplicità sia $p in P$ dove $P$ è l'insieme dei numeri primi. Devo procedere per passi successivi (similmente ad un algoritmo)!

Operiamo come segue:

$x=q_x*phi(p)+r_x$

ed analizziamo, suponendo $r_x!=0$:

$a^(q_x*phi(p)+r_x)-=(a^(q_x))^phi(p)*a^(r_x)(phi(p))-=a^(r_x)(p)$

Per il piccolo teorema di Fermat!

Ora se r_x è pari, consideriamo $r_x=2rho_(p1)$ ($rho_(p1)<r_x$) ed allora valutiamo:

$(b/p)-=b^((p-1)/2)(p)$

Se questo è congruo a $1(p)$ allora proseguiamo e troviamo

$beta_0: beta_0^2=b(p)$

Se è congruo a $-1(p)$ allora non ci sono soluzioni.

Se $r_x$ è dispari consideriamo $r_x=2rho_(d1)+1$ ($rho_(d1)<r_x$) ed allora valutiamo

$((ba^(-1))/p)-=(ba^(-1))^((p-1)/2)(p)$

Se questo è congruo a $1(p)$ allora proseguiamo e troviamo

$gamma_0: gamma_0^2=ba^(-1)(p)$

Se è congruo a $-1(p)$ allora non ci sono soluzioni.

Proseguiamo rispettivamente il discorso poi considerando le equazioni:

$a^(rho_(p1))-=beta_0(p)$

oppure:

$a^(rho_(d1))-=gamma_0(p)$

questi passi hanno comunque una fine ($NN$ ha un minimo!!!), visto che $rho$ diminuisce di volta in volta.

Penso che questo sia un buon modo per risolvere il tutto! La soluzione è sempre $mod phi(p)$

Qualche commento?

[Lord K]

Ora, visto che il post mi interessa particolarmente, tento una risoluzione del seguente esercizio per vedere se quanto ho trovato funziona:

$5^x=8 mod 11$

Per aiutarmi riporto i residui quadratici $mod 11$: ${1,4,9,5,3,3,5,9,4,1}$ ed in ogni caso seguo quanto sopra!

$(8/11)=8^(10/2)-=-1(11)$

Quindi per $x$ pari non ho soluzione, sia allora $x$ dispari e considero quindi:

$(gamma_0)^2-=8*[5]^(-1)(11)-=8*9(11)-=6(11)$

In questo caso si vede già che non ci sono soluzioni, visto che:

$(6/11)-=6^5-=-1(11)$

Almeno pare funzionare nel caso non ci sia tale numero

[Lord K]

Tentiamo allora per:

$5^x-=3 (11)$

Abbiamo:

$(3/11)-=3^5-=1(11)$

$beta_0^2-=3(11) rightarrow beta_0={(beta_(01)=5),(beta_(02)=6):}$

Primo caso:

$beta_(01)=5$ allora la nuova equazione è:

$5^(rho_(01))-=5(11)$

con $rho_(01)-=1(11)$ da qui la soluzione al nostro dilemma è: $x=2(10)$

Secondo caso:

$beta_(02)=5$ allora la nuova equazione è:

$5^(rho_(02))-=6(11)$

si vede subito che $rho_(02)$ non è pari, quindi:

$(gamma_1)^2-=6*[5]^(-1)-=6*9-=10(11)$

ed anche qui non ci sono soluzioni ($gamma_1$ è pari!).

Unica soluzione quindi $x-=2(10)$