Equazioni discrete

[leone81]

Ciao a tutti,

avrei bisogno di indicazioni su come risolvere equazioni a soluzioni discrete, del tipo

1. $2^x = a mod n$, con $a$ ed $n$ noti
2. $ax^2 + bx + c = 0 mod n$.

dove $x$ è un intero.
Qualcuno può darmi una mano?

Grazie

[Lord K]

Ben trovato!

Per la prima equazione io direi che potresti provare a vedere il mio post sul Logaritmo discreto sempre in questa parte del forum.

Per la seconda invece si segue un procedimento simile alla risoluzione standard:

$ax^2+bx+c \equiv 0 (n)$

1-Sia $a,2$ invertibile:

$x^2+b(a^(-1))x+c(a^(-1)) \equiv 0 (n)$

Allora:

$(x+alpha)^2 = x^2 + 2alphax + alpha^2$

da cui:

$2alpha = b(a^(-1))$
$alpha^2 = c(a^(-1))$

Ovvero esiste una soluzione se:

$[b(a^(-1))]^2 = 4*c(a^(-1))$

Ed è:

$alpha = b(a^(-1))(2^(-1))$

Se invece ce ne sono due:

$x^2 + b(a^(-1))x + [b(a^(-1))(2^(-1))]^2 - [b(a^(-1))(2^(-1))]^2 + c(a^(-1)) \equiv 0 (n)$

$(x + b(a^(-1))(2^(-1)))^2 \equiv [b(a^(-1))(2^(-1))]^2 - c(a^(-1)) (n)$

Ora chiamiamo $gamma = [b(a^(-1))(2^(-1))]^2 - c(a^(-1))$ e $delta = x + b(a^(-1))(2^(-1))$, si tratta di risolvere il problema:

$delta^2 \equiv gamma (n)$

Ovvero basta conoscere i residui quadratici di $n$ e poi si trovano le due soluzioni (ammesso che esistano).

2-Nel caso in cui $a,2$ non siano invertibili allora $GCD(a,n)!=1$ o $GCD(n,2)=2$

Allora:

$ax^2+bx+c=lambda*n$

sia $GCD(a,n)=D_0$ e sia $D_1 = n/(D_0)$

$D_1(ax^2+bx+c)=(lambda*D_1)*n$
$(D_1a)x^2 + (D_1b)x + (D_1c) = (lambda*D_1)*n$

allora questa "finta" equazione di secondo grado diventa una più semplice di primo:

$(D_1b)x + (D_1c) = (lambda*D_1)*n+ (D_1a)x^2 $

Visto che il termine a destra è sempre divisibile per $n$:

$(D_1b)x + (D_1c) \equiv 0 (n)$

[leone81]

ok, grazie mille!

ciao.

[leone81]

Ciao Lord K,

approfitto della tua disponibilità ... potresti provare a risolvere questa equazione o, almeno, spiegarmi come la risolveresti? io c'ho provato, ma non ci riesco
L'equazione è $x^2 - 164x + 71 = 0 mod(253)$.

Grazie mille.
ciao

[Lord K]

"leone81":Ciao Lord K,

approfitto della tua disponibilità ... potresti provare a risolvere questa equazione o, almeno, spiegarmi come la risolveresti? io c'ho provato, ma non ci riesco
L'equazione è $x^2 - 164x + 71 = 0 mod(253)$.

Grazie mille.
ciao

Seguo il ragionamento sopra:

Osserviamo che $GCD(253,2)=1$

$x^2 - 2*82x+ 82^2-82^2+71 \equiv 0(253)$
$(x-82)^2 \equiv 6653(253)$
$(x-82)^2 \equiv 75(253)$

ora sappiamo che $253 in P$ con $P$ insieme dei primi. Calcoliamo allora il simbolo di Legendre per vedere se è un residuo quadratico:

$(75/253) = (15/253)*(5/253) = (3/253)*(5/253)*(5/253) = (3/253) $

Da qui legge di reciprocità quadratica:

$(3/253) =(253/3)*(-1)^((253-1)/2*(3-1)/2) = (253/3) = 1$

Quindi abbiamo di certo soluzione al problema.

Con un bel poco di conti (sostanzialmente tentativi) vedo che le soluzioni di $delta^2 \equiv 3 (253)$ sono $4$:

${(x_1=16),(x_2=39),(x_3=214),(x_4=237):}$

allora:

$(x-82)^2 \equiv (x_i)^2*5^2(253)$

la prima genera:

$(x-82)^2 \equiv (16*5)^2(253)$
${(x-82 \equiv 80 (253)),(x-82 \equiv -80 (253)):} Rightarrow {(x \equiv 162 (253)),(x\equiv 2 (253)):} $

la seconda:

$(x-82)^2 \equiv (39*5)^2(253)$
${(x-82 \equiv 195 (253)),(x-82 \equiv -195 (253)):} Rightarrow {(x \equiv 24 (253)),(x\equiv -113(253)):} $

la terza e la quarta le rigenerano infatti $-39\equiv 214(253)$ e $-16\equiv237(253)$

Soluzioni al problema principale:

${(x \equiv 162 (253)),(x\equiv 2 (253)),(x \equiv 24 (253)),(x\equiv -113(253)):}$

Verifico:

$162^2-164*162+71 = -2*162+71 = -324+71=-253 \equiv 0(253)$
$2^2-164*2+71 = -162*2+71 =-253 \equiv 0(253)$
$24^2 - 164*24 + 71 = -24*140 +71 = -3289 = -253*13 \equiv 0(253)$
$(-113)^2 - 164*(-113) + 71 = 113*277+71 = 31372 = 253*124 \equiv 0(253)$

e quindi decisamente ci siamo... puff...puff...pant....pant...

[leone81]

Grazie!

ti chiederei alcune cose ...
tu hai scritto prima $delta^2 \equiv 3 (253)$ e $(x-82)^2 = (x_i)^2*5^2 (253)$, ma il $3$ e il $5$ derivano dal calcolo del simbolo di Legendre?

se fossi vincolato a soluzioni del tipo $x = 2^i$, qualche indicazioni su come calcolare $i$ ?

Grazie 1000

[Lord K]

"leone81":Grazie!

ti chiederei alcune cose ...
tu hai scritto prima $delta^2 \equiv 3 (253)$ e $(x-82)^2 = (x_i)^2*5^2 (253)$, ma il $3$ e il $5$ derivano dal calcolo del simbolo di Legendre?

No, derivano dal $75$ che è $3*5^2$

se fossi vincolato a soluzioni del tipo $x = 2^i$, qualche indicazioni su come calcolare $i$ ?

Grazie 1000

Se cerchi sempre $modp$ diciamo che la risoluzione è algoritmica. come nel post che ti ho citato sopra del logaritmo discreto. Ti faccio un esempio: risolviamo:

$2^x \equiv 5(7)$

Allora dapprima trovo i residui $mod7$:

${1,4,2,2,4,1}$

non essendo $5$ presente, allora $x non può essere pari, quindi necessariamente deve essere dispari, allora $x=2x_0+1$

$2^(2(x_0)+1) \equiv 5 (7)$
$(2^(x_0))^2 \equiv 5*2^(-1)$

dove $2^(-1) = 4$ allora l'equazione diventa:

$(2^(x_0))^2 \equiv 5*4 (7)$
$(2^(x_0))^2 \equiv 6 (7)$

che risulta impossibile visto che 6 non è un residuo quadratico.

Altro esempio (salto i commenti)

$2^x \equiv 4 (13)$

$R={1,4,9,10,12,10,10,12,10,9,4,1}$

allora $x$ pari implica:

$2^(2(x_0))\equiv 10 (13)$

${(2^(x_0) \equiv 2(13)),(2^(x_1) \equiv -2(13)):}$

La prima ha soluzione:

$x_0 \equiv 1(13)$

e la seconda deve essere necessariamente $x_1$ dispari:

$(2^(x_2))^2 \equiv -2*2^(-1) (13)$
$(2^(x_2))^2 \equiv -1 (13)$
$(2^(x_2))^2 \equiv 12 (13)$

e da qui si prosegue come sopra.... fino a trovare tutte le soluzioni.