Calcolatore Simbolo di Legendre e Jacobi (Residui Quadratici)

Calcolatore simbolo di Legendre (a/p) e Jacobi, test residui quadratici mod p primo, conteggio QR/NR, verifica radici primitive in teoria dei numeri elementare.

Parametri di calcolo
Questo calcolatore ti è stato utile?

Simbolo di Legendre: definizione

Il simbolo di Legendre (a/p), introdotto da Adrien-Marie Legendre nel 1798, e una funzione fondamentale della teoria dei numeri che caratterizza i residui quadratici. Per p primo dispari e a intero:

(a/p) = +1 se a e residuo quadratico mod p (esiste x con x^2 = a mod p)
(a/p) = -1 se a e non-residuo quadratico
(a/p) = 0 se p divide a

Calcolo via criterio di Eulero: (a/p) = a^((p-1)/2) mod p, dove il risultato e 1 (per +1), p-1 (per -1) o 0.

Esempio numerico

(3/7): calcolare 3^((7-1)/2) mod 7 = 3^3 mod 7 = 27 mod 7 = 6 = -1 mod 7. Quindi (3/7) = -1, ovvero 3 NON e un quadrato modulo 7. Verifica diretta: i quadrati mod 7 sono {1^2, 2^2, 3^2} mod 7 = {1, 4, 2}; 3 non e in questa lista.

QR e NR mod p

Per ogni primo p > 2, esattamente (p-1)/2 elementi di (Z/pZ)* sono residui quadratici (QR) e (p-1)/2 sono non-residui (NR). Esempio p = 7:

  • QR = {1, 2, 4} (= {1^2, 3^2, 2^2} mod 7).
  • NR = {3, 5, 6}.

Esempio p = 11: QR = {1, 3, 4, 5, 9}, NR = {2, 6, 7, 8, 10}. I QR formano un sottogruppo di indice 2 in (Z/pZ)* sotto moltiplicazione: QR * QR = QR, QR * NR = NR, NR * NR = QR.

Reciprocita quadratica (Gauss 1796)

Il teorema di reciprocita quadratica, considerato il "gioiello" della teoria dei numeri da Gauss, lega (p/q) e (q/p) per primi dispari distinti p, q:

(p/q)(q/p) = (-1)^((p-1)/2 * (q-1)/2)

Equivalentemente: se p o q e congruo a 1 mod 4, allora (p/q) = (q/p). Altrimenti (entrambi 3 mod 4): (p/q) = -(q/p).

Leggi supplementari:

  • (-1/p) = +1 se p = 1 mod 4, -1 se p = 3 mod 4.
  • (2/p) = +1 se p = +/- 1 mod 8, -1 se p = +/- 3 mod 8.

Simbolo di Jacobi

Il simbolo di Jacobi (a/n) generalizza Legendre a moduli n dispari positivi (anche composti). Definizione: se n = p1^e1 * p2^e2 * ... * pk^ek allora:

(a/n) = (a/p1)^e1 * (a/p2)^e2 * ... * (a/pk)^ek

Per n primo: Jacobi = Legendre. Per n composto: (a/n) = 1 NON implica che a sia QR mod n. Esempio: (2/15) = (2/3)(2/5) = (-1)(-1) = 1 ma 2 non e QR mod 15. Tuttavia, Jacobi e calcolabile in O(log n) tramite reciprocita generalizzata, senza fattorizzare n. Usato in test di primalita Solovay-Strassen.

Calcolo efficiente del simbolo di Jacobi

Algoritmo iterativo basato su reciprocita generalizzata:

  1. Riduci a mod n.
  2. Se a = 0: (a/n) = 0 se n != 1, altrimenti 1.
  3. Estrai fattori 2 da a: ogni fattore 2 contribuisce con (2/n), che si calcola via n mod 8.
  4. Reciprocita: (a/n) = (n/a) * sign basato su a, n mod 4.
  5. Ripeti con (n mod a, a). Termina quando uno e 1.

Costo O(log min(a, n)). Notevolmente più veloce della fattorizzazione + Eulero per ogni fattore.

Radici primitive

Un intero g e radice primitiva mod n se l ordine di g in (Z/nZ)* e phi(n). Per p primo: phi(p) = p - 1. Esistenza: ogni p primo ha radici primitive (teorema di Gauss). Numero di radici primitive: phi(phi(n)). Test: g e radice primitiva mod p sse g^((p-1)/q) != 1 mod p per ogni primo q che divide p - 1.

Esempio: p = 7, p - 1 = 6 = 2 * 3. Verifica per g = 3: 3^3 mod 7 = 6 != 1, 3^2 mod 7 = 2 != 1. Quindi 3 e radice primitiva mod 7. Le radici primitive mod 7 sono {3, 5} (phi(6) = 2).

Applicazioni

  • Crittografia: test di primalita (Solovay-Strassen, Miller-Rabin).
  • RSA: scelta primi p, q con condizioni sui residui.
  • Diffie-Hellman: scambio chiavi su gruppi ciclici (Z/pZ)*.
  • Curve ellittiche: residuosita per punti di gruppo.
  • Algoritmi di fattorizzazione: Quadratic Sieve usa relazione QR.
  • Teoria dei codici: codici lineari su Z/pZ.
  • Teoria delle equazioni: risoluzione x^2 = a mod p (Tonelli-Shanks).
  • Generatori pseudorandom: Blum-Blum-Shub, basato su QR.

Calcolo radici quadrate modulari

Quando (a/p) = 1, esistono esattamente due x con x^2 = a mod p (x e p - x). Trovarle:

  • Caso p = 3 mod 4 (semplice): x = a^((p+1)/4) mod p.
  • Caso p = 5 mod 8: usa formula esplicita Tonelli.
  • Caso p = 1 mod 8 (generale): algoritmo di Tonelli-Shanks, O(log^2 p).

Per p = 7 (3 mod 4): radici di 2 mod 7. Calcolare 2^((7+1)/4) = 2^2 = 4. Verifica: 4^2 = 16 = 2 mod 7. Altra radice: 7 - 4 = 3. Verifica: 3^2 = 9 = 2 mod 7. OK.

Storia

Eulero (1755): prime osservazioni sui residui quadratici, criterio di Eulero. Legendre (1798, Essai sur la theorie des nombres): introduce il simbolo (a/p) e formula la reciprocita quadratica come congettura. Gauss (1801, Disquisitiones Arithmeticae): prima dimostrazione rigorosa, ne fornira 8 dimostrazioni nella vita. Jacobi (1837): generalizzazione (a/n) per n composto. Eisenstein, Cauchy, Dirichlet: ulteriori dimostrazioni. Il teorema di reciprocita quadratica e considerato uno dei risultati più profondi della matematica del XIX secolo, generalizzato in classfield theory (Hilbert, Takagi, Artin).

Modalita del calcolatore

Cinque modalita: simbolo di Legendre (a/p) per p primo; simbolo di Jacobi (a/n) per n dispari; test diretto di residuo quadratico con elenco radici; conteggio totale QR e NR mod p; verifica candidato radice primitiva mod p. Output include metodo applicato, verifica numerica e proprietà strutturali.

Aggiornato a luglio 2026

Domande frequenti

Cos'e il simbolo di Legendre?

E una funzione (a/p) introdotta da Legendre nel 1798 che caratterizza i residui quadratici modulo un primo dispari p: vale +1 se a e un residuo quadratico (esiste x con x^2 = a mod p), -1 se non lo e, e 0 se p divide a. E uno strumento centrale della teoria dei numeri elementare.

Cos'e un residuo quadratico?

Un numero a e residuo quadratico modulo p se esiste un intero x tale che x^2 sia congruo ad a modulo p, cioe se a e un "quadrato" nell'aritmetica modulare. Per un primo dispari p, esattamente (p-1)/2 dei numeri da 1 a p-1 sono residui quadratici e gli altri (p-1)/2 sono non residui.

Cos'e il criterio di Eulero?

E la formula che permette di calcolare il simbolo: (a/p) = a^((p-1)/2) mod p, dove il risultato e +1 oppure p-1 (interpretato come -1). Eulero dimostro che a e residuo quadratico se e solo se a^((p-1)/2) e congruo a 1 modulo p. E il metodo diretto usato dal calcolatore.

Cos'e la legge di reciprocita quadratica?

E il teorema che lega i simboli di due primi dispari distinti: (p/q)(q/p) = (-1)^(((p-1)/2)((q-1)/2)). Congetturata da Legendre e dimostrata rigorosamente da Gauss (che ne diede otto dimostrazioni), permette di calcolare rapidamente i simboli riducendo iterativamente i numeri, come nell'algoritmo di Euclide.

Che differenza c'e fra simbolo di Jacobi e di Legendre?

Il simbolo di Jacobi (a/n) generalizza quello di Legendre a moduli n dispari qualsiasi, anche composti, come prodotto dei simboli di Legendre sui fattori primi. Attenzione: per n composto un valore di Jacobi +1 non garantisce che a sia un residuo quadratico, a differenza del caso primo.

Cos'e una radice primitiva?

E un elemento g il cui ordine modulo p e esattamente p-1, cioe le cui potenze generano tutti gli interi da 1 a p-1 modulo p. Ogni primo ammette radici primitive (teorema di Gauss) e il loro numero e phi(p-1). Si verifica controllando che g^((p-1)/q) non sia 1 per ogni primo q che divide p-1.

A cosa serve nel test di primalita?

Il test di Solovay-Strassen usa il simbolo di Jacobi: per un primo n vale sempre (a/n) = a^((n-1)/2) mod n, mentre molti composti violano questa congruenza. Verificandola su piu basi casuali si individuano i composti con alta probabilita, e un numero che supera molte prove e primo con probabilita altissima.

Dove si usa in crittografia?

I residui quadratici sono alla base del cifrario di Goldwasser-Micali, la prima cifratura a chiave pubblica dimostrabilmente sicura, e del crittosistema di Rabin, la cui sicurezza equivale alla fattorizzazione di un intero di Blum. In questi schemi decidere se un numero e residuo quadratico modulo un composto e computazionalmente difficile.

Formula

Legendre: (a/p) = a^((p-1)/2) mod p (Euler). Reciprocity: (p/q)(q/p) = (-1)^((p-1)(q-1)/4). Jacobi: (a/n) = product (a/pi)^ei. Primitive root: ord(g) = phi(n).

Commenti (0)

Ancora nessun commento. Sii il primo!