Questions from Dixon Factorization Paper I read the first page of Asymptotically Fast Factorization of Integers, and have a few questions.
Quotes from the paper are formatted as blockquotes (>).

Following Legendre, we know that there exist integers x and y which
  are relatively prime to n and such that x^2 == y^2 (mod n), 
  but x != y or -y.

From what I read about coprime integers, two numbers, x and y, are relatively prime if they only share 1 as an even divisor.
Example: 4 and 9 are co-prime since: 


*

*4's factors: {1, 2, 4}

*9's factors: {1, 3, 9}



For such integers GCD(n, x+y) is a proper factor of n.
Our search for the integers x and y is carried out in two stages. First we look for squares z^2 which are congruent (mod n) to integers whose prime factors all lie in some set P.

Is this set, P, equivalent to a bound? For example, if the bound is 7, then the set, P, consists of all prime numbers up to and including 7?
So, a bound of 7 yields: P = {2,3,5,7}.
Lastly, if N = 5995, what is the work to carry out the first stage?
Given the set of [1..5995], we'd only include numbers, i.e. we filter on numbers whose prime factors consist solely of set P, {2,3,5,7}?
Once we've filtered those numbers, we then check if, for each number, its squared value (mod 5995) == 0?
 A: First, one of the more useful tools for dealing with elementary arithmetic is the Chinese remainder theorem. It states that, if $p, q$ are coprime, then any set of two equations $x \equiv a \pmod{p}, x \equiv b \pmod{q}$ has a (unique) solution modulo $pq$.
In your case, this means that, if $n$ is not a prime power, it has a factorization $n = pq$ with $p$, $q$ coprime and both $\neq 1$; then pick any number $y$, the set of two equations (in $x$)
$$ x \equiv y \pmod{p}, \quad x \equiv -y \pmod{q}$$
has a unique solution (by the existence property of the Chinese remainder theorem), which I shall write $x \pmod{pq}$. Then we may check that $x^2, y^2$ satisfy the relation
$$ x^2 \equiv y^2 \pmod{p}, \quad x^2 \equiv y^2 \pmod{q},$$
which, by the unicity property of the Chinese remainder theorem, implies that $x^2 \equiv y^2 \pmod{pq}$. Since however $x \not\equiv y \pmod{q}$, we have $x \not \equiv y \pmod{pq}$; likewise, since $x \not \equiv -y \pmod{p}$, we have $x \not \equiv y \pmod{pq}$. This proves your first quote.
Now assume that $n = pq$ with $p, q$ unknown, and let $x, y$ be such a pair of integers (known). The crucial fact is that the relations $x^2 \equiv y^2, x \not\equiv y, x \not \equiv -y$ do not depend on the unknown values $p, q$.
You then have:
 - $n= pq$ divides $x^2 - y^2$;
 - $n= pq$ does not divide $x - y$;
 - $n= pq$ does not divide $x + y$;
which means that in the (unknown) pair $p, q$, one of them (say $p$) divides (only) $x-y$, and the other divides (only) $x + y$, and both of them divide $n$ of course.
We may therefore recover $p$ from the values $n$ and $x-y$: it is the GCD of $n$ and $x-y$. (This is computable in polynomial time using Euclid's algorithm).
For the equivalence between the set of prime factors and the bound: this is not a full equivalence. Since you need a finite set of auxiliary primes, such a set is always bounded. But you could want, for some reason, to use only some of those primes. In practice this is not the case, when factoring using the quadratic sieve there is no reason to “throw away” elements of the smoothness basis. On the contrary, you need as many primes as possible (to improve the probability that $z$ is smooth relative to your basis), as small as possible (to improve the speed of your computations).
For your 5995 example: it is a bit of a strange example since this number is obviously already dividble by 5, which is an element of any reasonable smoothness basis. Instead I will work out the case of $18419$.
By random generation I find the following relations:
$$\begin{split}
148^2 &\equiv 5 \times 17 \times 41\\
139^2 &\equiv 2 \times 11 \times 41\\
685^2 &\equiv 2 \times 5^4 \times 7\\
887^2 &\equiv -1 \times 2 \times 41\\
235^2 &\equiv -1 \times 2^5\\
622^2 &\equiv 5 \times 17\\
955^2 &\equiv -1 \times 3 \times 5^2 \times 7 \times 17\\
56^2 & \equiv 2^6 \times 7^2\\
525^2 & \equiv -1 \times 2^2 \times 3 \times 5 \times 11\\
869^2 & \equiv -1 \times 2 \times 3^2
\end{split}$$
from which we get the relation:
$$ (235 \times 869)^2 \equiv (-1)^2 \times 2^6 \times 3^2, \quad\text{or}\quad 1606^2 \equiv 24^2 \pmod{18419}.$$
This means that $18419$ divides $(1606-24) \times (1606+24)$. We check by hand that it divides neither factor, and we may compute
$$ \gcd (18419, 1606-24) = 113,$$
which is a proper divisor of $18419$.
A: As you know, Fermat's insight was to represent $N$ as a difference of two squares, $$N = A^2 - B^2$$We can factor this expression to $N = (A + B)(A - B)$, which gives us a factorization of $N$, namely $A+B$ and $A-B$.
Fermat's method näively searches for this difference of squares by letting $f(x) = x^2 - N$ and trying values of $x$ until we find that $f(x) = B^2$ is a perfect square. Then we let $A = x$ and compute the factors $A \pm B$. This is terribly inefficient: slower than trial division in the worst case!
Dixon's insight was that instead of searching for a pair of squares, we can construct one directly from things that are easier to find. In particular, we let $f(x) = x^2 - N$ as before, but instead of looking for $f(x) =$ "perfect square," we just look for $f(x) =$ "a number with small factors." This begs a couple of questions:


*

*What is even remotely helpful about finding such a thing?

*How small is "small"?


To answer these questions, suppose we have a list of integers:
$$\begin{align}J & = 3 \cdot 3 \cdot 5 \cdot 7 \\
K & = 2 \cdot 3 \cdot 11 \\
L & = 5 \cdot 7 \cdot 7 \cdot 7 \\
M & = 2 \cdot 2 \cdot 5 \cdot 5 \cdot 5 \cdot 5\end{align}$$
Q: Is any of these a perfect square?A: Well, $J,K$ and $L$ aren't.
Q: How can you tell?A: That's easy! Each of their prime factors appears an odd number of times.
Q: What about $M$?