Given a large integer n you compute k = s(n-1)/2 (mod n) and find that k != +/-1. You then compute x = k2 (mod n). Prove that if x != 1 then n is not prime, and that if x = 1 then we can factor n.