Residuo quadratico
Ciao a tutti.
Come da titolo, una domanda sui residui quadratici.
C'è un modo per trovare, dato un numero $n$, tutti i residui quadratici modulo $n$?
Diciamo che un posso, con alcune regole, determinare se un certo numero è residuo quadratico o meno modulo $n$, se però ho bisogno di conoscerli tutti, fare i vari casi a mano è complicato se $n$ è grande.
Grazie in anticipo, buon fine settimana a tutti
Ciao.
Come da titolo, una domanda sui residui quadratici.
C'è un modo per trovare, dato un numero $n$, tutti i residui quadratici modulo $n$?
Diciamo che un posso, con alcune regole, determinare se un certo numero è residuo quadratico o meno modulo $n$, se però ho bisogno di conoscerli tutti, fare i vari casi a mano è complicato se $n$ è grande.
Grazie in anticipo, buon fine settimana a tutti
Ciao.
Risposte
Puoi sfruttare vari accorgimenti per scrivere un algoritmo di crivello che, dato un intero $n \ge 1$, determini tutti e soli i residui quadratici mod n nell'insieme $A_n = \{1, 2, \ldots, n\}$, i.e. ogni $a \in A_n$ per cui l'equazione $x^2 = a$ mod n è compatibile - per esempio, osservando che $a \in A_n$ è residuo quadratico sse lo stesso può dirsi di n-a, così da dimezzare il carico complessivo di lavoro, nel caso in cui $n$ sia un primo della forma 4k+1. Tuttavia, se cerchi una formula magica - o qualcosa che le si avvicini - in grado di restituirti l'insieme $U_n \subseteq A_n$ dei residui quadratici modulo n, mettiti l'anima in pace: forse neppure esiste, e di sicuro non è nota. Tanto più che gli elementi di $U_n$ possiedono una distribuzione piuttosto randomatica nell'intervallo [1,n].
"Gabriel":
osservando che $a \in A_n$ è residuo quadratico sse lo stesso può dirsi di n-a, così da dimezzare il carico complessivo di lavoro.
Grazie.
Non mi torna comunque la frase citata.
Tu dici: se $a$ è residuo quadratico, allora anche $n-a$ lo è, ovvero, dico io, $-a$
Prendi quest'esempio: ho da controllare se $2$ è residuo quadratico mod7
$a^2\equiv2\(mod7)$
Usando Eulero
$2^((7-1)/2)\equiv1\(mod7)$ perciò la risposta è sì.
Lo stesso non si può dire di $7-2$, ovvero $-2$, giacché
$(-2)^((7-1)/2)=-8\equiv-1\(mod7)$, cioè è un non residuo.
Ho preso qualche abbaglio?
Un vuoto terminologico: cosa intendi per "algoritmo di crivello"?
Ciao & grazie.
Mea culpa, avevo in mente i primi della forma 4k+1 - edito subito. Per il resto, un algoritmo di crivello è, appunto, un algoritmo in grado di scremare da un insieme tutti gli elementi che non soddisfano una determinata proprietà. Questo è il caso, per esempio, del (celebre) crivello di Eratostene, che opera su $NN$, separando i primi dai composti.
C'e' una importante assunzione detta "Quadratic Residuosity Assumption", QRA, che recita piu' o meno cosi':
Detti $p,q$ primi "grandi", $n=pq$, e $a$ coprimo con $n$ tale che $(\frac{a}{n})=1$ (dove $(\frac{.}{.})$ e' il simbolo di Jacobi),
e' "difficile" decidere se $a$ e' un residuo quadratico modulo $n$.
In altre parole, non si conoscono algoritmi efficienti nemmeno per decidere un solo residuo, figuriamoci trovarli tutti
p.s. ovviamente se $n$ e' primo, basta calcolare il simbolo di legendre
Detti $p,q$ primi "grandi", $n=pq$, e $a$ coprimo con $n$ tale che $(\frac{a}{n})=1$ (dove $(\frac{.}{.})$ e' il simbolo di Jacobi),
e' "difficile" decidere se $a$ e' un residuo quadratico modulo $n$.
In altre parole, non si conoscono algoritmi efficienti nemmeno per decidere un solo residuo, figuriamoci trovarli tutti
p.s. ovviamente se $n$ e' primo, basta calcolare il simbolo di legendre
"vl4d":
In altre parole, non si conoscono algoritmi efficienti nemmeno per decidere un solo residuo, figuriamoci trovarli tutti
Va bene, basta saperlo
Purtroppo ancora non conosco il simbolo di Jacobi, ma solo quello di Legendre.
Per il resto, un algoritmo di crivello è, appunto, un algoritmo in grado di scremare da un insieme tutti gli elementi che non soddisfano una determinata proprietà.
Perfetto, ti ringrazio.
La domanda originario comunque mi è venuta perché vedo spesso, specialmente nell'oliforum, dire, per restringere i casi di un problema: modulo tot, i residui quadratici sono.... (i modulo è comunque un numero piccolo).
In questi casi, si fanno i conti a mano oppure esiste magari una tavola che raccoglie i residui di, che so, i primi $n$ naturali?
Grazie.
Da qualche parte esisteranno pure delle tabelle (disponendo di un accesso a JSTOR, per esempio, vi si trova una tabella dei residui quadratici di tutti i primi $< 2350$). Resta il fatto che, dato un modulo $m$ ragionevolmente piccolo, si può ricavare il set completo dei residui quadratici modulo m calcolando - senza grossi sforzi - l'immagine della funzione $NN \cap [0,m-1] \to ZZ$ / $mZZ: x \to x^2$.
Ok, lo terrò a mente quando studierò cosa è l'immagine di una funzione (sto ancora al liceo). 
Ti chiedo l'ultima cortesia: tempo fa avevo aperto un topic che però non ha ricevuto alcuna risposta
https://www.matematicamente.it/forum/res ... 28113.html
Visto che mi pari competente in materia, gli daresti un'occhiata? Magari si tratta di una domanda secca, come in questo caso, la cui risposta è che "non esiste un modo"
Grazie di nuovo,
ciao.
Ti chiedo l'ultima cortesia: tempo fa avevo aperto un topic che però non ha ricevuto alcuna risposta
https://www.matematicamente.it/forum/res ... 28113.html
Visto che mi pari competente in materia, gli daresti un'occhiata? Magari si tratta di una domanda secca, come in questo caso, la cui risposta è che "non esiste un modo"
Grazie di nuovo,
ciao.
Non è necessario che aspetti oltre. L'immagine di una funzione $f: X \to Y$, dove $X$ e $Y$ sono sottoinsiemi di un dato universo $U$, è l'insieme $f(X) = \{y \in Y: \exists x \in X\mbox{ t.c. }f(x) = y\}$. Detto questo, le mie competenze sono molto discutibili, per cui non è il caso che ti sbilanci troppo coi giudizi, senti a me.
"Gabriel":
Detto questo, le mie competenze sono molto discutibili, per cui non è il caso che ti sbilanci troppo coi giudizi, senti a me.
Va bene
Grazie di nuovo, magari appena mi libero un po' proverò a postare un esempio per vedere se sono in grado di applicare quello che mi hai detto.
Ciao.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo