Crittografia Probabilistica
J(x,n) = simbolo di Jacobi a valori {-1,+1}, mcd(x,n)=1.
Q[n] = insieme dei residui quadrati modulo n.
Si hanno le seguenti due relazioni:
- Se n è primo, x appartiene a Q[n] SSE J(x,n) = +1;
- Se n è composito, x appartiene a Q[n] allora J(x,n) = +1;
PQ[n] = insieme degli x non appartenenti a Q[n] ma tali che J(x,n) = +1 (pseudo-quadrati).
Proposizione: Se n=p q, allora |Q[n]| = |PQ[n]|. Inoltre, per ogni intero y in PQ[n] si ha che
- x residuo quadrato --> y x pseudo-quadrato (one-to-one)
Sia n= p q, il problema dei residui quadrati consiste nello stabilire se x , con J(x,n) =1, é uno pseudo-quadrato oppure un residuo quadrato.
Se la fattorizzazione di n è nota, allora il problema dei residui quadrati si risolve in tempo polinomiale, altrimenti è difficile anche con la randomizzazione (~ fattorizzare).