Harristotelian Logic

Quadratic residues and factoring are intimately related using some basic congruences. And there is a uniqueness property with residues which appears to have been missed by practitioners in various math disciplines that consider factoring.

This unique key is critical in determining quadratic residues by using factoring.

With k^2 = q mod p, where p is an odd prime, consider that with:

f_1 = ak mod p, and f_2 = bk mod p

where 'a' and 'b' are natural numbers, with T = f_1*f_2 = abk^2 mod p, you can simply add f_1 and f_2, to get:

f_1 + f_2 = (a+b)k mod p, and solve for k with:

k = (a+b)^{-1}(f_1 + f_2) mod p

assuming a+b is coprime to p. So you can find k, by factoring T, where since k^2 = q mod p, and T = abk^2 mod p, you have:

T = abq mod p.

But where is this unique key?

Well one reason some have wrongly assumed that congruences are useless with factoring is the product ab can have as its factors ANY non-zero residue of p; however, there is a sum involved here, which is a+b.

Now ask, with some other residues 'c' and 'd', can ab = cd mod p, and a+b = c+d mod p? That answer is, no.

Proof:

ab = cd mod p, and a+b = c+d mod p, so a = c+d-b mod p, and substituting:

b(c+d-b) = cd mod p, so b^2 = bc + bd - cd mod p.

But notice, b^2 - bc = bd - cd, gives b(b-c) = d(b-c) mod p, gives b = d mod p. (Choice comes from b-c, as if b=c, then a divide by zero error.)

So 'a' and 'b' are equal to 'c' and 'd'.

Then you have a UNIQUE KEY for 'a' and 'b'.

So, k = (a+b)^{-1}(f_1 + f_2) mod p, uniquely identifies f_1 = ak mod p, and f_2 = bk mod p, where T = abq mod p, when q is a quadratic residue modulo p.

Given that T = abq mod p is selected for particular factors by a+b and ab, one may wonder why this approach would ever fail to find k, but that is easily answered.

For instance if ak<p and bk < p, but abk^2 > p and q is small compared
to it, then T = abq mod p, may be too small at lower values for T, and only work for higher ones.

Also if ak < p and bk < p, then f_1 and f_2 would have k as a factor, so only when T had k as a factor could you have a solution.

So you'd have solutions with T = abk^2 + pk. So there are rules that will block solutions with certain T's.

Then remarkably there is a simple way to solve for quadratic residues using factoring, where a unique key is part of that solution.

Given a quadratic residue q, modulo p, you can find k, such that k^2 = q mod p, by finding T = abq mod p, where 'a' and 'b' are natural numbers you choose, from:

k = (a+b)^{-1}(f_1 + f_2) mod p

where f_1*f_2 = T.

Here that solution is uniquely associated with a particular factorization of T—despite congruences—by a+b and ab.