Quadratic Residues

Let $n$ be a positive integer and let $a$ be an integer such that $gcd(a, n) = 1$.

$a$ is said to be a quadratic residue modulo $n$ if and only if there exists a $x$ such that: $x² \equiv a (mod n)$

When $n$ is a prime number $(n = p)$ there exist three cases:

1. either $a$ is a multiple of $p$, or

2. $a$ is a quadratic residue, or

3. $a$ is not a quadratic residue.

The Legendre symbol $(\frac{a}{p})$ captures this as follows.

Legendre Symbol

Jacobi Symbol

Counts

For a prime $p$, the number of integers belonging to the set $[1, 2, . . . , p − 1]$ that are quadratic residues is exactly $(p − 1)/2$.

a(n)=local(v,s);v=vector(eulerphi(n));s=0;\
for(k=1,n,if(gcd(k,n)==1,s=s+1;v[s]=k;););return(v);
qr(n)=local(v);v=a(n); /* number (#) of true quadratic residues */\
return(length(Set(vector(length(v),k,(v[k]^2)%n))));
j(n)=local(v,c);v=a(n); /* # of true or fake quadratic residues */\
return(sum(k=1,length(v),kronecker(v[k],n)==1));
f(n)=return([eulerphi(n),qr(n),j(n)]);
f(101) /* returns [100,50,50] */
f(103) /* returns [102,51,51] */
f(107) /* returns [106,53,53] */
f(109) /* returns [108,54,54] */

How about composite numbers that are the product of two distinct prime numbers?

f(13*17) /* returns [192,48,96] --- half are fakes! */
f(11*13) /* returns [120,30,60] --- half are fakes! */
f(11*19) /* returns [180,45,90] --- half are fakes! */

Square Roots

Example:

p=11; q=19; n=p*q; r=20; a=lift(Mod(r^2,n));
rp=lift(Mod(a,p)^((p+1)/4)); rq=lift(Mod(a,q)^((q+1)/4));
r1=lift(chinese(Mod( rp,p),Mod( rq,q))); /* 20, (r1/p)=+1, (r1/q)=+1 */
r2=lift(chinese(Mod( rp,p),Mod(-rq,q))); /* 75, (r2/p)=+1, (r2/q)=-1 */
r3=lift(chinese(Mod(-rp,p),Mod( rq,q))); /* 134, (r3/p)=-1, (r3/q)=+1 */
r4=lift(chinese(Mod(-rp,p),Mod(-rq,q))); /* 189, (r4/p)=-1, (r4/q)=-1 */

Factorization

Example (continuation of the code of the previous slide):

p=11; q=19; n=p*q;
r1=20; r2=75; r3=134; r4=189; /* square roots of 191 */
gcd(r1-r2,n);                 /* 11 */
gcd(r1+r2,n);                 /* 19 */

pari-gp can only compute square roots when the modulus is prime:

sqrt(Mod(5,11))    /* ok (because 5 is a quadratic residue)     */
sqrt(Mod(9,14))    /* error (because the modulus is not prime)  */