Simbolo di Legendre

Dato un numero primo dispari \( p \) e un numero intero \( a \), il simbolo di Legendre \(\left(\frac{a}{p}\right)\) è definito come \[ \left(\frac{a}{p}\right) =\begin{cases}  \phantom{-}1 & \text{se \( a \) è un residuo quadratico} \\ -1 & \text{se \( a \) non è un residuo quadratico} \\ \phantom{-}0 & \text{se } p \text{ divide } a \end{cases} \]

Si tratta di una funzione matematica che mi dice se un numero intero $ a $ è un residuo quadratico in un modulo $ n $. A seconda dei casi, sostituisce il simbolo di Legendre con 1, -1 oppure 0.

Cos'è un residuo quadratico?

Il numero $ a $ è un residuo quadratico se esiste un intero \( x \) tale che $$ x^2 \equiv a \pmod{p} $$ In altre parole, $ a $ è un residuo quadratico se è il quadrato di un numero intero modulo $ n $. Viceversa, se non esiste, allora $ a $  non è un residuo quadratico.

Vale la pena sottolineare che il simbolo di Legendre si utilizza solo quando il modulo è un numero primo.

Se il modulo è un numero composto si ricorre al simbolo di Jacobi.

Nota. Il simbolo di Legendre è utilizzato nei test di primalità, come il test di Solovay-Strassen, e nelle applicazioni della crittografia, specialmente negli algoritmi basati su residui quadratici. E' usato anche per verificare i numeri pseudoprimi di Eulero.

Un esempio pratico

Prendo come esempio questo simbolo di Legendre.

$$ \left(\frac{4}{7}\right) $$

Poiché \( 4 = 2^2 \) è un quadrato, deduco che esiste un numero intero \( x = 2 \) tale che \( x^2 \equiv 4 \pmod{7} \).

Quindi, il simbolo di Legendre diventa 1

\[ \left(\frac{4}{7}\right) = 1 \]

Esempio 2

Ora considero quest'altro simbolo

$$ \left(\frac{3}{7}\right) $$

Devo verificare se esiste un numero \( x \) tale che \( x^2 \equiv 3 \pmod{7} \).

Controllo i quadrati modulo \( 7 \):

• \( 0^2 = 0 \equiv 0 \pmod{7} \)
• \( 1^2 = 1 \equiv 1 \pmod{7} \)
• \( 2^2 = 4 \equiv 4 \pmod{7} \)
• \( 3^2 = 9 \equiv 2 \pmod{7} \)
• \( 4^2 = 16 \equiv 2 \pmod{7} \)
• \( 5^2 = 25 \equiv 4 \pmod{7} \)
• \( 6^2 = 36 \equiv 1 \pmod{7} \)

Nessuno di questi è congruo a \( 3 \), quindi \( 3 \) non è un residuo quadratico modulo \( 7 \).

Quindi, il simbolo di Legendre diventa -1

\[ \left(\frac{3}{7}\right) = -1 \]

Esempio 3

Considero quest'ultimo caso

$$ \left(\frac{7}{7}\right) $$

Poiché \( 7 \) è divisibile per sé stesso (\( 7 \equiv 0 \pmod{7} \)), il simbolo di Legendre diventa zero.

\[ \left(\frac{7}{7}\right) = 0 \]

Nota. Questo metodo di calcolo per elencazione dei quadrati è molto chiaro ed è utile per spiegare il concetto. Tuttavia, diventa impraticabile quando il modulo è un numero molto grande. In questo caso è preferibile calcolare il simbolo di Legendre usando il criterio di Eulero.

Il criterio di Eulero

Questa formula mi permette di capire se un numero intero \( a \) è un residuo quadratico nel modulo \( p \) senza dover calcolare tutti i quadrati.

Esempio 1

Devo verificare se $ a=4 $ è un residuo quadratico nel modulo $ p=7 $.

$$ \left(\frac{4}{7}\right) $$

Per saperlo utilizzo la formula di Eulero.

\[ \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p} \]

In questo caso $ a=4 $ e $ p = 7 $ quindi il simbolo di Legendre è:

\[ \left(\frac{4}{7}\right) \equiv 4^{\frac{7-1}{2}} \pmod{7} \]

\[ \left(\frac{4}{7}\right) \equiv 4^{\frac{6}{2}} \pmod{7} \]

\[ \left(\frac{4}{7}\right) \equiv 4^3 \pmod{7} \]

\[ \left(\frac{4}{7}\right) \equiv 64  \pmod{7} \]

\[ \left(\frac{4}{7}\right) \equiv 1 \pmod{7} \]

Il simbolo di Legendre è 1, questo significa che 4 è un residuo quadratico modulo 7.

Esempio 2

Devo verificare se $ a=3 $ è un residuo quadratico nel modulo $ p=7 $.

$$ \left(\frac{3}{7}\right) $$

Utilizzo la formula di Eulero.

\[ \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p} \]

\[ \left(\frac{3}{7}\right) \equiv 3^{\frac{7-1}{2}} \pmod{7} \]

\[ \left(\frac{3}{7}\right) \equiv 3^{\frac{6}{2}} \pmod{7} \]

\[ \left(\frac{3}{7}\right) \equiv 3^3 \pmod{7} \]

\[ \left(\frac{3}{7}\right) \equiv 27 \pmod{7} \]

\[ \left(\frac{3}{7}\right) \equiv 6 \pmod{7} \]

Il risultato è 6, e ricordando che 6 modulo 7 equivale a -1, significa che:

\[ \left(\frac{3}{7}\right) \equiv -1 \pmod{7} \]

Il simbolo di Legendre è -1, ciò significa che 3 non è un residuo quadratico modulo 7.

Proprietà del simbolo di Legendre

Il simbolo di Legendre ha le seguenti proprietà:

• Moltiplicatività
  Se \( a, b \) sono interi, allora il simbolo di Legendre è moltiplicativo rispetto al numeratore. \[ \left(\frac{a b}{p}\right) = \left(\frac{a}{p}\right) \cdot \left(\frac{b}{p}\right) \]

  Esempio. Se voglio calcolare \( \left(\frac{6}{7}\right) \), posso spezzarlo in: \[ \left(\frac{6}{7}\right) = \left(\frac{2}{7}\right) \cdot \left(\frac{3}{7}\right) \] Poi calcolare separatamente i simboli di Legendre. A volte la scomposizione è utile. In particolar modo, se già conosco il risultato di qualche fattore o se mi conviene utilizzare la legge di reciprocità quadratica sui singoli simboli per semplificare i calcoli.

• Legge di reciprocità quadratica
  Questa è una delle proprietà più potenti per calcolare il simbolo di Legendre senza dover fare tutti i quadrati modulo \( p \). Dice che, se \( p \) e \( q \) sono numeri primi, allora: \( p \) e \( q \): \[  \left(\frac{q}{p}\right) = (-1)^{\frac{(p-1)(q-1)}{4}} \cdot \left(\frac{p}{q}\right) \]

  Esempio. Voglio calcolare \( \left(\frac{3}{11}\right) \), che è un po' scomodo perché dovrei verificare tutti i quadrati modulo \( 11 \). Uso invece la reciprocità quadratica. Scambio numeratore e denominatore usando una formula inversa su un singolo fattore: \[ \left(\frac{3}{11}\right) = (-1)^{\frac{(11-1)(3-1)}{4}} \cdot \left(\frac{11}{3}\right) \] Semplifico l'esponente \[ \left(\frac{3}{11}\right) = (-1)^{\frac{10 \cdot 2}{4}} \cdot \left(\frac{11}{3}\right) \] $$ \left(\frac{3}{11}\right) = (-1)^5 \cdot \left(\frac{11}{3}\right) $$ $$ \left(\frac{3}{11}\right) = (-1) \cdot \left(\frac{11}{3}\right) $$ Il simbolo di Legendre \( \left(\frac{11}{3}\right) \) equivale a \( \left(\frac{2}{3}\right) \) perché \( 11 \equiv 2 \pmod{3} \) $$ \left(\frac{3}{11}\right) = (-1) \cdot \left(\frac{2}{3}\right) $$ In questo modo posso calcolare una semplice congruenza in modulo 3 anziché 11. Sapendo che \( 2 \equiv -1 \pmod{3} \)  posso sostituire  \( \left(\frac{2}{3}\right) = -1 \). \[ \left(\frac{3}{11}\right) = (-1) \times (-1) = 1 \] Il risultato è \( 1 \), quindi \( 3 \) è un residuo quadratico del modulo \( 11 \). Per fare una rapida verifica basta calcolare il quadrato di 5 modulo 11, è equivalente a 3. $$ 5^2 = 25 \equiv 3 \pmod{11} $$ Ciò che conta è che applicando questa proprietà ho ottenuto il risultato finale (1) senza dover calcolare tutti i quadrati modulo 11. Il che è un gran bel vantaggio.

• Valori notevoli
  Per definizione si pone $$ \left( \frac{0}{p} \right) = 0 $$ Lo zero non è un residuo quadratico modulo p, e il simbolo di Legendre assume valore 0 se e solo se il numeratore è divisibile per il denominatore. $$ \left( \frac{1}{p} \right) = 1 $$ Il numero 1 è sempre un quadrato modulo qualsiasi numero primo p.

E così via.