Consider the following problem: - Input: n : positive integer - Output: number o
ID: 3796984 • Letter: C
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.
T2 mod 6 z z-, mod b 6-0 14341 1-0 1 2 3 4 5Explanation / 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;
}