Logaritmo discreto
Sia $a,b,c in ZZ$, vogliamo calcolare $x$ tale che:
$a^x-=b mod c$
scritto anche come:
$a^x-=b(c)$
$a^x-=b mod c$
scritto anche come:
$a^x-=b(c)$
Risposte
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)
$(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)
$((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?
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)
$(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)
$((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?
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
$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

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)$
$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)$