Unique factor key and quadratic residues

[JSH]

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.

James Harris