Consider the following problem: - Input: n : positive integer - Output: number o

Question

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 x2 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.

Explanation / Answer

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;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.