If x2 is divisible by a prime squared, such as 49, divide x by 7 (mod n). Finally you have an x whose square is a product of small primes, such that no prime is repeated.
When searching for these "relations", choose x equal to the square root of kn for small values of k. This keeps x2 close to the square root of n (mod n), whence x2 is more likely to be smooth.
If x2 is smooth except for one large prime factor, you may want to retain this one as well. This is called a partial relation.
Gathering up these relations lends it self to distributed computing, including various FactorAtHome efforts, which is how the really big composites are cracked. A server hands out ranges of x for clients to examine, or clients can select x at random. Relations are passed back to the server for analysis.
Each relation consists of an x, and a boolean vector with a 1 representing each prime in x2. eventually a subset of relations is larger than the primes needed to support it. Working over the field Z2, some linear combination of these vectors yields 0. Multiply the corresponding values of x together and call the result v. Note that v2 consists of various primes raised to even powers. Cut these exponents in half and call the result w. Thus v2 = w2, so run gcd(v±w,n) to extract a factor of n. If v and w are equal or opposite, gather a few more relations and try again.
Note, this algorithm runs forever if n is a prime power, since each element has at most two square roots, and these are opposite mod n.
entire books have been written on this subject. There are many variations, such as the multiple polynomial quadratic sieve (mpqs), which uses polynomials other than x2. In "constant shifting", n is multiplied by a small number k, whence kn factors into (kp)×q faster than n would split into p×q. Other tricks help find relations faster, while fine-tuned heuristics determine which partial relations, with anomalous large primes, are worth keeping. These mathematical modifications and software optimizations are beyond the scope of this web page.
At this point I am going to close this topic, with the understanding that other primality tests and factoring algorithms do exist, for the integers, and for other ufds. But I think I've hit the highlights.