Elimination

Finding the subset of y’s

Consider the finite field of two elements, 0 and 1. It is called “GF(2)”. Consider a b dimensional vector space over GF(2). A vector in this space is expressed as a string of b bits. Addition of vectors is bitwise exclusive or. We will take b to be the size of our prime base.

If we multiply (y_i = p₁^e_i1 p₂^e_i2 ...) by (y_j = p₁^e_j1 p₂^e_j2 ...) we get
(y_iy_j = p₁^e_i1+e_j1 p₂^e_i2+e_j2 ...)

If we gather the parities of the exponents of the successive primes into a bit string we get a vector in our vector space. Addition of these vectors corresponds to multiplication of the y’s. Each y yields such a vector. If we can find a subset of the vectors whose vector sum is zero, then the corresponding subset of y’s will multiply out to a product of primes where all of the prime exponents will be even. This allows us to learn the square root of this number. (Halve each exponent and multiply again.)

Finding this subset of vectors is like solving a set of linear equations. The field of rationals are where we solve linear equations with rational coefficients. GF(2) is where we solve above problem, substituting bits for rationals or floating point numbers

Solving linear equations is the same in any field. Actually it is easier here for there are no problems with illconditioned matrices.