Residui quadratici
Ho un problemino, perchè ho una dimostrazione sbagliata su uno Zero Knowledge Protocol basato sui residui quadratici. Il succo della questione è questo:
A sostiene di conoscere la fattorizzazione di $n=p*q$ con $p-=q-=3$ $mod 4$
B inventa un numero $x in ZZ/(nZZ)$ e calcola $x^4=c$ mod n inviando $c$ ad A
A deve risolvere il sistema $y^2-=c$ $ mod n$ e lo risolve perchè conosce p e q (basta che ad es. mod p calcola $c^((p+1)/4)$ poi fa lo stesso mod q e poi risolve 4 sistemi con il teorema cinese)
qui arriva il problema perchè la mia dimostrazione dice che le soluzioni di $y^2-=c$ $mod n$ sono $x^2, -x^2, omega*x^2, -omega*x^2$ e fin qui tutto ok, ma dice che $omega^2-=-1$ $ mod n$ che è ovviamente impossibile(deve essere .$omega^2-=1$ $ mod n$).
Partendo da questo presupposto sbagliato dimostra che l'unico quadrato mod n tra le quattro soluzioni è $x^2$.
Quello che vi chiedo è se c'è un modo (giusto) per dimostrare che l'unico quadrato tra le quattro soluzioni è $x^2$
A sostiene di conoscere la fattorizzazione di $n=p*q$ con $p-=q-=3$ $mod 4$
B inventa un numero $x in ZZ/(nZZ)$ e calcola $x^4=c$ mod n inviando $c$ ad A
A deve risolvere il sistema $y^2-=c$ $ mod n$ e lo risolve perchè conosce p e q (basta che ad es. mod p calcola $c^((p+1)/4)$ poi fa lo stesso mod q e poi risolve 4 sistemi con il teorema cinese)
qui arriva il problema perchè la mia dimostrazione dice che le soluzioni di $y^2-=c$ $mod n$ sono $x^2, -x^2, omega*x^2, -omega*x^2$ e fin qui tutto ok, ma dice che $omega^2-=-1$ $ mod n$ che è ovviamente impossibile(deve essere .$omega^2-=1$ $ mod n$).
Partendo da questo presupposto sbagliato dimostra che l'unico quadrato mod n tra le quattro soluzioni è $x^2$.
Quello che vi chiedo è se c'è un modo (giusto) per dimostrare che l'unico quadrato tra le quattro soluzioni è $x^2$
Risposte
Per caso stai facendo crittografia a Padova con Languasco? 
Evidentemente un tale $omega$ non esiste perché essendo p e q congrui a 3 mod 4, essi non 'ammettono' radici quadrate di -1. Precisamente:
Lemma 1: sia $p$ un numero primo dispari. Allora esiste un numero intero $z$ tale che $z^2 equiv -1\ mod(p)$ se e solo se $p equiv 1\ mod(4)$.
Ti consiglio di procedere così: innanzitutto ti convinci che vale il seguente
Lemma 2: se p e q sono due numeri primi distinti e a,b sono due interi allora $a equiv b\ mod(pq)$ se e solo se $a equiv b\ mod(p)$ e $a equiv b\ mod(q)$.
In tutto il seguito $x$ è un elemento fissato non nullo di $ZZ//nZZ$, dove $n=pq$, dove p e q sono due numeri primi distinti congrui a 3 modulo 4.
Ora prendi la tua equazione $y^2-x^4 equiv 0\ mod(pq)$ nell'incognita $y$, e la riscrivi come $(y-x^2)(y+x^2) equiv 0\ mod(pq)$. Il lemma 2 ci dice che risolvere questa equazione è equivalente a risolvere il seguente sistema:
$\{(y equiv pm x^2\ mod(p)),(y equiv pm x^2\ mod(q)):}$
infatti quando lavori "modulo un primo" l'equazione $(y-x^2)(y+x^2)=0$ ha come uniche soluzioni $y=x^2$ e $y=-x^2$ (perché sei in un campo).
I quattro sistemi che dovrai risolvere saranno dunque i seguenti:
(1) $\{(y equiv x^2\ mod(p)),(y equiv x^2\ mod(q)):}$ (2) $\{(y equiv -x^2\ mod(p)),(y equiv -x^2\ mod(q)):}$ (3) $\{(y equiv x^2\ mod(p)),(y equiv -x^2\ mod(q)):}$ (4) $\{(y equiv -x^2\ mod(p)),(y equiv x^2\ mod(q)):}$
Il sistema (1) ha $y = x^2\ mod(pq)$ come unica soluzione, il (2) ha $y=-x^2\ mod(pq)$ come unica soluzione (per via del lemma). Rimangono da comprendere meglio i sistemi (3) e (4). Ora, per il teorema cinese del resto esiste un'unica soluzione ai sistemi (3) e (4) modulo $pq$. Sia $a$ la soluzione di (3) modulo $pq$, e sia $b$ la soluzione di (4) modulo $pq$.
Quello che vogliamo mostrare è che $-x^2$, $a$, $b$ non sono quadrati modulo $pq$. Ora:
1) se $-x^2$ fosse un quadrato modulo pq, diciamo $-x^2=z^2$ modulo $pq$, allora in particolare $(z/x)^2 equiv -1\ mod(p)$ (essendo x non nullo, esso è invertibile modulo p). Ciò è impossibile perché essendo p congruo a 3 modulo 4, non esistono radici quadrate di -1 in $ZZ//pZZ$ (lemma 1).
2) se $a$ fosse un quadrato modulo pq, diciamo $a=z^2$ modulo $pq$, allora $z^2 equiv -x^2\ mod(q)$ per costruzione, ma ciò di nuovo implica $(z/x)^2 equiv -1$ modulo $q$, assurdo (vedi punto 1).
3) analogo al punto 2.
Dunque ne deduciamo che l'unica soluzione di $y^2 equiv x^4\ mod(pq)$ che è un quadrato modulo $pq$ è $y=x^2$.
Evidentemente un tale $omega$ non esiste perché essendo p e q congrui a 3 mod 4, essi non 'ammettono' radici quadrate di -1. Precisamente:
Lemma 1: sia $p$ un numero primo dispari. Allora esiste un numero intero $z$ tale che $z^2 equiv -1\ mod(p)$ se e solo se $p equiv 1\ mod(4)$.
Ti consiglio di procedere così: innanzitutto ti convinci che vale il seguente
Lemma 2: se p e q sono due numeri primi distinti e a,b sono due interi allora $a equiv b\ mod(pq)$ se e solo se $a equiv b\ mod(p)$ e $a equiv b\ mod(q)$.
In tutto il seguito $x$ è un elemento fissato non nullo di $ZZ//nZZ$, dove $n=pq$, dove p e q sono due numeri primi distinti congrui a 3 modulo 4.
Ora prendi la tua equazione $y^2-x^4 equiv 0\ mod(pq)$ nell'incognita $y$, e la riscrivi come $(y-x^2)(y+x^2) equiv 0\ mod(pq)$. Il lemma 2 ci dice che risolvere questa equazione è equivalente a risolvere il seguente sistema:
$\{(y equiv pm x^2\ mod(p)),(y equiv pm x^2\ mod(q)):}$
infatti quando lavori "modulo un primo" l'equazione $(y-x^2)(y+x^2)=0$ ha come uniche soluzioni $y=x^2$ e $y=-x^2$ (perché sei in un campo).
I quattro sistemi che dovrai risolvere saranno dunque i seguenti:
(1) $\{(y equiv x^2\ mod(p)),(y equiv x^2\ mod(q)):}$ (2) $\{(y equiv -x^2\ mod(p)),(y equiv -x^2\ mod(q)):}$ (3) $\{(y equiv x^2\ mod(p)),(y equiv -x^2\ mod(q)):}$ (4) $\{(y equiv -x^2\ mod(p)),(y equiv x^2\ mod(q)):}$
Il sistema (1) ha $y = x^2\ mod(pq)$ come unica soluzione, il (2) ha $y=-x^2\ mod(pq)$ come unica soluzione (per via del lemma). Rimangono da comprendere meglio i sistemi (3) e (4). Ora, per il teorema cinese del resto esiste un'unica soluzione ai sistemi (3) e (4) modulo $pq$. Sia $a$ la soluzione di (3) modulo $pq$, e sia $b$ la soluzione di (4) modulo $pq$.
Quello che vogliamo mostrare è che $-x^2$, $a$, $b$ non sono quadrati modulo $pq$. Ora:
1) se $-x^2$ fosse un quadrato modulo pq, diciamo $-x^2=z^2$ modulo $pq$, allora in particolare $(z/x)^2 equiv -1\ mod(p)$ (essendo x non nullo, esso è invertibile modulo p). Ciò è impossibile perché essendo p congruo a 3 modulo 4, non esistono radici quadrate di -1 in $ZZ//pZZ$ (lemma 1).
2) se $a$ fosse un quadrato modulo pq, diciamo $a=z^2$ modulo $pq$, allora $z^2 equiv -x^2\ mod(q)$ per costruzione, ma ciò di nuovo implica $(z/x)^2 equiv -1$ modulo $q$, assurdo (vedi punto 1).
3) analogo al punto 2.
Dunque ne deduciamo che l'unica soluzione di $y^2 equiv x^4\ mod(pq)$ che è un quadrato modulo $pq$ è $y=x^2$.
grazie martino. Devo fare l'esame di crittografia... però a tor vergata!
Mi era tutto chiaro, tranne il fatto che a e b non fossero quadrati. Tuttora però non riesco a capire perchè $a =-x^2$ $mod q$
Mi era tutto chiaro, tranne il fatto che a e b non fossero quadrati. Tuttora però non riesco a capire perchè $a =-x^2$ $mod q$
"miles_davis":
grazie martino. Devo fare l'esame di crittografia... però a tor vergata!
Ah ok, chiedevo perché ricordo che c'era qualche errore del genere nel libro di Languasco...
non riesco a capire perchè $a =-x^2$ $mod q$
$a$ è per costruzione una soluzione del sistema (3). Osservane la seconda equazione
scusa la domanda idiota... Ora mi è tutto chiaro. Grazie mille. A presto. 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo