Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In wikipedia source: http://en.wikipedia.org/wiki/Quadratic_residue

under "composite modulus" section

I found the line "On the other hand, if we want to know if there is a solution for x less than some given limit c, this problem is NP-complete;however, this is a fixed-parameter tractable problem, where c is the parameter."

what does it mean by "given limit c , and fixed parameter tractable with c as parameter". Does this mean regardless of large values are given for c as a limit , we can solve the quadratic congruence without knowing the factorization? or does it has any other meaning?
what is the limit of c such that we cannot solve quadratic congruence using fpt

If i am wrong or obscure in my question, please notify me.

share|improve this question

2 Answers 2

That Wikipedia article isn't very clear about what the inputs are and how their size is modelled. I'd understand the passage you cite to refer to the fact that for fixed $c$ the complexity of finding a square root $x$ with $x^2=a\pmod n$ is polynomial in $a$ and $n$ since you just have to square $c$ different values and the complexity of squaring is polynomial in $a$ and $n$.

share|improve this answer
    
Thanks joriki . "you just have to square c different values", thats where i got a doubt. that I would like know , if the bit sizes of n and c are considerably very large , can we say "just have to" square c different values. what i mean is , Is it still an FPT problem while considering c as a parameter? –  smslce Oct 12 '12 at 12:37
    
@user1665835: Squaring a number takes time quadratic in the number of bits, and the bit sizes of all residues to be squared are at most that of $n$, so the time complexity is bounded by $c$ times the square of the bit size of $n$. The bit size of $c$ doesn't matter when we're considering $c$ as a fixed parameter. –  joriki Oct 12 '12 at 12:51
    
:thank you joriki. I got (not all but) some understanding of my question –  smslce Oct 12 '12 at 13:19

We don't need to square every number below $c$!

If $a$ is a quadratic residue $\pmod{n}$, we can say if there is some positive integer $x<c$ that satisfy

$$ x^2 = kn + a $$

through a sieve. We have $k\leq\lfloor\frac{c^2}{n}\rfloor=K$ and $kn+a$ is a square, so it is a quadratic residue for every prime $p$. Let $N_p$ be the set of non-quadratic residues $\pmod{p}$: we can get rid of any $k\in[0,K]$ such that $kn+a\in N_p$; so, by taking about $\log K$ primes and sieving, only a limited number of potential solutions remain and has to be checked.

share|improve this answer
    
:Thanks Jack D'Aurizio. It cleared a lot. –  smslce Oct 12 '12 at 14:38
    
:I know 'am missing some important point. So , what i understood is, it requires only ((∑(p=0 to floor(logK))N_p) * log(K)) values to obtain the set of potential solutions. Then , even if we set c near to n, it should be easy to compute the solutions of x value. If that's the picture, then why cant we compute x for given a , such that x^2=a(mod n), provide n is a very very large(ex: a 400 digit number) composite number . What i am i missing here? –  smslce Oct 12 '12 at 15:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.