Using the “Relations”

Let M represent the set of numbers y_i where we know how to express y_i² as kn+(product of elements of the prime base). We will have collected at this point many elements of M, indeed as many as there are elements in the prime base. In fact we will mainly (exclusively?) collect such values where k = −1. We will know or may easily enough compute this factorization.

M is closed under multiplication. This follows from thinking of it is an exercise modulo n. From this point on our reasoning and code are all modulo n. The square of each number y_i in our collection is a product of our small primes with non negative exponents:

y_i² = p₁^e_i1 p₂^e_i2 ...

We have as many y_i’s as small primes. We can find a subset of the y_i²’s which, when multiplied together, have exponents that are all even. Call this product S. We can find x such that x² = S.

Recall that the y_i’s were themselves quadratic residues and that we can find solve x_i = y_i(mod n) for the subset of y_i’s.