Consider the following problem:

- Input: n: positive integer

- Output: number of quadratic nonresidues modulo n, where a quadratic nonresidue mod n is an integer r in the range of 0 to n - 1 such that there is no integer x in this range where x² mod n = r.

For example, the quadratic nonresidues of n = 6 are 2 and 5, as shown by the table below:

Thus, the solution for n = 6 is 2.

1. Give pseudocode for an algorithm to compute the number of quadratic nonresidues mod n. Your algorithm should be as efficient as possible. Be sure to describe which data structure(s) you're using and why.

T2 mod 6 z z-, mod b 6-0 14341 1-0 1 2 3 4 5