CONGRUENZA QUADRATICA BINARIA X² ≡ A (MODULO P Numero primo)

X² ≡ A  (MODULO P Numero primo)
Risolvere questa congruenza significa trovare, se esiste, un quadrato esatto tale che il resto della sua divisione per il numero primo P, sia A.
Ricordiamo che, in Teoria dei Numeri, si definisce residuo quadratico di un numero primo P proprio il resto della divisione di un quadrato esatto per P.
I numeri primi hanno la notevole proprietà di avere esattamente (P-1)/2 residui quadratici e (P-1)/2 non residui quadratici.
Per quanto detto, questa congruenza avrà soluzioni solo se A è un residuo quadratico di P.
Per stabilire se un intero A sia residuo quadratico di un numero primo P, si usa il criterio di Eulero (useremo il simbolo ” ^ ” per indicare “elevato a”):
Se  A^[(P-1)/2] ≡ 1 (modulo P), allora A è residuo quadratico di P.
Se  A^[(P-1)/2] ≡ -1 (modulo P), allora A è non residuo quadratico di P.
Una volta accertato che A è un residuo quadratico di P, siamo certi che la congruenza ha soluzione.
Fissiamo subito un punto fondamentale:
Se A è un residuo quadratico del numero primo P, la congruenza quadratica binaria  X² ≡ A  ha sempre due soluzioni (ovviamente inferiori a P). Se chiamiamo queste due soluzioni M ed N, allora saranno tali che  M + N  =  P.
Spesso queste soluzioni vengono chiamate radici quadrate di A modulo P.
Dato che A deve essere un residuo quadratico di P, per quanto detto, dovrà essere:
A^[(P-1)/2] ≡ 1
Moltiplichiamo primo e secondo membro per A:
A*A^[(P-1)/2] ≡ A
A^[1 + (P-1)/2] ≡ A
A^[(2 + P -1)/2] ≡ A
A^[(P + 1)/2] ≡ A
A questo punto basta trovare il numero X tale che:
X² = A^(P + 1)/2
Che è ovviamente:
X = A^(P + 1)/4
Potremmo pensare di aver così risolto la congruenza, ma purtroppo ciò è vero solo nel caso in cui (P + 1)/4 sia un numero intero.
Ci può però consolare la considerazione che questo avviene per il 50% dei numeri primi.
Ricordiamo che i numeri primi si dividono in due grandi famiglie: quelli che diviso 4 danno come resto 1 e quelli che diviso 4 danno per resto 3. Non esistono altre possibilità.
I primi avranno forma P = 4k + 1 ed i secondi P = 4k + 3.
Ebbene, per questa seconda famiglia, l’espressione (P + 1)/ 4 è un numero intero:
(P + 1)/4 = (4k + 3 +1)/4 = (4k + 4)/4 = k +1
TEOREMA:
Se P è un numero primo della forma 4K + 3 ed A un suo residuo quadratico, la congruenza quadratica  X² ≡ A  (modulo P) ha due soluzioni:
M = A^(k + 1) modulo P ed N = P – M
Risolviamo ad esempio la congruenza:
X² ≡ 2 (modulo 23)
2 è residuo quadratico di 23, in quanto:
2^11 = 2048 e 2048 modulo 23 = 1
23 è della forma 4k + 3, infatti 23 = 4*5 +3 e sarà k = 5
M = A^(k+1) = 2^(5 + 1) = 2^6 = 64
M = 64 modulo 23 = 18
N = P – M = 23 – 18 = 5
Dunque le due soluzioni della congruenza saranno 18 e 5
Verifichiamo:
18² = 324
324 : 23 = 14 con resto 2
5² = 25
25 : 23 = 1 con resto 2
Si può però risolvere la congruenza anche nel caso di P = 4k + 1.
I numeri primi della forma 4k + 1 si possono dividere in due grandi famiglie: quelli delle forme 8s + 1 ed 8s + 5.
Per questi ultimi abbiamo la soluzione, però dobbiamo distinguere 2 casi:
Se A^[(P-1)/4] ≡ 1 (modulo P), allora una soluzione è:
M = A^(s + 1)
Se A^[(P-1)/4] ≡ -1 (modulo P), allora una soluzione è:
M = [2^(2s + 1)] * A^(s + 1)
Facciamo un esempio:
Si voglia risolvere la congruenza:
X² ≡ 7 (modulo 29)
7 è un residuo quadratico di 29 (fidatevi ….)
29 è della forma (8s + 5), infatti 29 = 8*3 + 5 ed s sarà 3
A^[(P-1)/4] = 7^(28/4) = 7^7 = 823543
823543 modulo 29 = 1, quindi siamo nel primo caso.
M = A^(s + 1) = 7^(3+1) = 7^4 = 2401
M = 2401 modulo 29 = 23
N = P – M = 29 – 23 = 6
Dunque le due soluzioni della congruenza saranno 23 e 6
Verifichiamo:
23² = 529
529 : 29 = 18 con resto 7
6² = 36
36 : 29 = 1 con resto 7
Se P è della forma 8s + 1, anche in questo caso esistono due famiglie per una delle quali esiste la soluzione e così via all’infinito ….