Unique factor key and quadratic residues

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
.

Relevant Pages

  • Re: JSH: Results that are much more fun
    ... FLT years earlier--and not saying I DID prove FLT, ... reversed equations, or reversed equations and later realized I wasn't, ... and found that I could solve quadratic residues mod p. ... T, instead of S, though it IS it would seem surrogate factoring. ...
    (sci.math)
  • Re: Results that are much more fun
    ... used them with no success against the factoring problem. ... It's like taking over the definition of mathematical proof ... Ok, so I worked on surrogate factoring for years with little success, ... and found that I could solve quadratic residues mod p. ...
    (sci.math)
  • SF: Quadratic residues
    ... surrogate factoring. ... quadratic residues. ... you can make it more likely that the algorithm will ... factor by multiplying your target by some large prime--hopefully larger ...
    (sci.crypt)
  • SF: Quadratic residues
    ... surrogate factoring. ... quadratic residues. ... you can make it more likely that the algorithm will ... factor by multiplying your target by some large prime--hopefully larger ...
    (sci.math)