8. **Primality test based on quadratic residues** Assume that there is an efficient algo-

rithm Jacobi

(a, n) that outputs

• 0 if gcd

(a, n) > 1,

• 1 if a ∈ Q_n, and

• -1 otherwise

(such an algorithm does exist). Assume further that the output of Jacobi

(a, n) is equal to a^{(n - 1)/2} mod n whenever gcd

(a, n) = 1 and n is an odd prime (this is indeed the case and is known as Euler's criterion).

(a) Design a probabilistic algorithm for primality testing based on the test function Jacobi

(a, n).

(b) Use the fact from Exercise 7(a)(ii) to specify a lower bound for false positives

(i.e., program executions that falsely classify n as being prime).