If someone here understands the Quadratic Sieve Algorithm, I'm having trouble understanding why every prime $p$ in the factor base needs to a prime such that $n$ is a quadratic residue modulo $p$. It is explained on the bottom of page 2 of the paper found here.

The sentence I'm struggling on is near the bottom of page 2, where it says

Now if $x$ is in this sieving interval, and if some prime $p$ divides $Q(x)$, then $(x − \lfloor \sqrt{n} \rfloor)^2 ≡ n ($mod $p)$.

Why is this statement true?


Since $Q(x)$ is defined as $(x+\lfloor \sqrt{n} \rfloor)^2 -n $, that follows directly from this definition.

The comments below show that I jumped too soon. However, looking more closely at the paper, I am inclined to agree with Thomas Andrews that this is indeed a typo.

I've looked at $(x+\lfloor \sqrt{n} \rfloor)^2 -(x-\lfloor \sqrt{n} \rfloor)^2 =4x\lfloor \sqrt{n} \rfloor $, but this doesn't seem to help.

  • 1
    $\begingroup$ How do you get from ($x + \lfloor \sqrt{n} \rfloor )^2$ to ($x - \lfloor \sqrt{n} \rfloor )^2$ here? $\endgroup$ – Jimm Nov 27 '15 at 7:09
  • $\begingroup$ Please show me because for some reason I can't see exactly how it does. $\endgroup$ – Jimm Nov 27 '15 at 7:12
  • 1
    $\begingroup$ Since the author only appears to use that formula to show thatn $n$ is a quadratic residue, modulo $p$, it would appear that the minus sign in the paper was a typo. $\endgroup$ – Thomas Andrews Nov 27 '15 at 7:20
  • $\begingroup$ I found this paper link and it seems that the it should have been $x + \lfloor \sqrt n \rfloor)^2$ $\endgroup$ – steven gregory Jan 17 '16 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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