Reading Jean-Luc Chabert's A History of Algorithms, I learned that Gauss, prompted by the poor state-of-the-art, designed two distinct methods for fast integer factorization.
Chabert's book discusses the first, the Method of Exclusions, and D.H. Lehmer gives a really nice explanation in his 1928 introduction of the Lehmer Sieve.
Those two documents plus a misleading MathWorld stub regarding solving Diophantine equations (which was evidently not its original purpose) are the only external references to Gauss' first method that I can find. I can't seem to find anything on the second.
Clarke's 1966 translation of the Disquisitiones Arithmeticae indicates that he actually considered his second method the superior of them (p.397), but I can't make heads or tails of his description. (pp.403-6)
Is there an explanation of Gauss' 2nd factorization method anywhere outside the Disquisitiones, or can anyone who understands it give a simple explanation?
Gauss's second factorization method is pretty much a take on the difference of squares method. If one finds $a^2 \equiv b^2 \ (\mathrm{mod} \ M)$, then either $\mathrm{gcd}(M,a+b)$ or $\mathrm{gcd}(M,a-b)$ is a non-trivial factor of M.
Gauss's genius idea was using quadratic forms to force a congruence of squares, by means of calculating the square root of the determinant (a quarter of the discriminant).
Considering D as the determinant of a quadratic form, if one has the following: $$\frac {x^2}{y^2} \equiv \frac {z^2}{w^2} \equiv D \ (\mathrm{mod} \ M),$$ it is possible to manipulate this congruence and obtain a congruence of squares. Gauss then used the uniqueness of the reduced forms of negative determinant and how one could calculate them all easily to calculate these "square roots".
For the time, it was an outstanding method, even though it requires a lot of calculations.