Consider the following problem Input n positive integer Ou

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

Solution

quadratic_residue(n)
{
   int a[n] --> array of size n.
   for(i =0;i<n;i++)
   {
       a[i] = 0;
   }
   for(i=0,j=n-1;i<=j;i++,j--)
   {
       tmp = (i*i)%n;
       a[tmp] = 1; --> Whenever we find a number as a quadratic residue. We make the corresponding value in array a to be 1.
   }
   for(i=0;i<n;i++)
   {
       if(a[i]==0)
       {
           return i;
       }
   }
   return -1;
}