I am reading The Joy of Factoring by Samuel Wagstaff and I am having trouble understanding a paragraph from this book. It says the following
One can use quadratic residues to speed Trial Division by skipping some primes that cannot be divisors. This device was used by Euler, Gauss, and others hundreds of years ago. Let N be the number to factor. Suppose we know a nonsquare quadratic residue r modulo N. Then r is also a quadratic residue modulo any prime factor p of N. If r is not a square, the Law of Quadratic Reciprocity restricts p to only half of the possible residue classes modulo 4|r|.
There are two things which I am not sure I understand correctly:
-When it says that a nonsquare quadratic residue mod $N$ is also a quadratic residue mod any prime factor $p$ of $N$. (I think this is because of the Chinese Remainder Theorem but I am not sure)
-When it says that if $r$ is not a square, the law of quadratic reciprocity restricts $p$ to only half of the possible residue classes modulo $4|r|$. I know that for example if $r$ is a quadratic residue mod $p$ then $p$ must also be a quadratic residue mod $m$ by the law of quadratic reciprocity, however this would restrict the possible values of $p$ to half of the residue classes mod $r$ not mod $4|r|$.
I am confused