Logaritmo discreto
Determinare k tale che $3^k-=8 (mod 65537)$.
(forza bruta?
)
(forza bruta?
)
Risposte
Un po' contoso, ma molto carino.
Prima di tutto osserviamo che questo $k$ esiste, dato che $3$ è una radice primitiva modulo $65537$; e che $F_4=2^{2^4}+1$, primo di Fermat. Abbiamo che $(3/65537)=(3/5)=-1$ - simbolo di Legendre - e che l'ordine di $3$ modulo $65537$ è $2^16$.
Inoltre, $2^16 \equiv -1 (mod65537)$, quindi il nostro $k$ sarà della forma $k=2^{16-5}m=2048m$, con $m \in {1,3,5,\ldots,31}$. A questo punto si ha $3^{2^11} \equiv 65529 \equiv -8 (mod65537)$. E ora ci serve calcolare $m$ tale che $(-8)^m=(-2)^{3m}\equiv 8 (mod65537)$. Quindi dobbiamo risolvere l'equazione $3m=16t+3$, con $t$ dispari, poiché si avrà $(-2)^{16t}*2^3 \equiv -(-1)*8 (mod65537)$. E si vede subito che l'intero $t$ più piccolo con tale proprietà è $3$, facendo avere $3m=51 \implies m=17+2^5n$. Quindi $k=2048(17+32n)$, con $n$ intero.
Prima di tutto osserviamo che questo $k$ esiste, dato che $3$ è una radice primitiva modulo $65537$; e che $F_4=2^{2^4}+1$, primo di Fermat. Abbiamo che $(3/65537)=(3/5)=-1$ - simbolo di Legendre - e che l'ordine di $3$ modulo $65537$ è $2^16$.
Inoltre, $2^16 \equiv -1 (mod65537)$, quindi il nostro $k$ sarà della forma $k=2^{16-5}m=2048m$, con $m \in {1,3,5,\ldots,31}$. A questo punto si ha $3^{2^11} \equiv 65529 \equiv -8 (mod65537)$. E ora ci serve calcolare $m$ tale che $(-8)^m=(-2)^{3m}\equiv 8 (mod65537)$. Quindi dobbiamo risolvere l'equazione $3m=16t+3$, con $t$ dispari, poiché si avrà $(-2)^{16t}*2^3 \equiv -(-1)*8 (mod65537)$. E si vede subito che l'intero $t$ più piccolo con tale proprietà è $3$, facendo avere $3m=51 \implies m=17+2^5n$. Quindi $k=2048(17+32n)$, con $n$ intero.
Ok
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo