Harristotelian Logic

Using very simple mathematics I've found a fascinatingly simple connection between the solution for a quadratic residue, and a factorization, where it is unbelievable how simple the mathematics is, so explaining it is trivial.

Given a quadratic residue q, modulo N, where N is odd, I've found that given

k^2 = q mod N

you can solve for k, with

k = a*(1 + 2a^2)^{-1}*(f_1 + f_2) mod N

where T = f_1*f_2 = (1 + a^2)*q + jN,

where j is a nonzero integer, where 'a' is a Natural number. And selecting 'a' can be critical to getting an answer quickly.

The equations come from z^2 = y^2 + T, x^2 = y^2 mod p, z = x + ak mod p, k = 2ax mod p, where p is a prime factor of N.

What makes this approach of interest is simply that k^2 is given in one equation and k is given in another, where solutions exist for any choice of 'a'—I remind 'a' is a Natural number—but the SIZE of f_1*f_2 needed to find the solutions is what varies depending on what 'a' is chosen.

My reason for taking this approach path originally was an attempt at factoring T by using another number, for which p is the factor, but it's easier to factor T, and use the luck of k^2 and k being given to you, in order to solve for k through that factorization.

Notice that with z^2 = y^2 + T, and x^2 = y^2 mod p, there are an infinity of solutions for x, for a non-trivial factorization which gives you one z and y.

The remaining two congruences, z = x + ak mod p and k = 2ax mod p, narrow that infinity down, and in so doing, allow you to define 'a' and k in such a way as to get k, given a quadratic residue modulo N, by factoring T.

The jump to N from p is rather straightforward, though that is remarkable as well that is is possible to make that jump.

The math is easy. Solutions exist for any 'a' if q is a quadratic residue, but finding them can be harder or easier dependent on 'a', as T may be relatively large for one 'a', while much smaller for another.

Weirdly enough there are 4 ruling congruences which I also call constraints which decide when T will work:

1. f_1 = ak mod p


2. f_2 = a^{-1}*(1 + a^2)*k mod p


3. z = (2a)^{-1}*(1 + 2a^2)*k mod p
   
   and


4. y = (2a)^{-1}*k mod p

If all of the above can be true without contradiction—for EACH prime factor p of N—then that T will work and give you k, where I remind k^2 = q mod N. An example of a contradiction is any two of the relations have k as a factor when T does not. That can often be about size, as if p is relatively large, so that f_1 = ak explicitly, and for some reason k is still a factor of any of the others despite the congruence relationship, then T must have k as a factor. A small T might not meet those conditions while there is some larger one that will.

Those 4 constraints are wild though because the mathematics is saying, hey, if you can fulfill these conditions, then ok, you get the right answer, if not, no.

So I came across this technique kind of by accident where there is just this oddity that the mathematics will solve for k^2 and k, so you can set k^2 = q mod N, and then go find k from factoring.

It can be wicked fast.

For example did a toy test bigger than I usually try, I picked p=91, and q=30, as 11^2 = 30 mod 91. With a=1, I have T = 60 mod 91.

My first try is with T=151, which is prime, and that didn't work (though trivial factorizations MAY work). If the first non-trivial factorization doesn't work then none will so I know not to try any others. Ok, next is:

T = 242, = 11(22), which works! k = 3^{-1}(11 + 22) mod 91 = 11 mod 91.

Here with ak less than p the math found an answer that fit the bill, though it can also use 91 - 11 that would be with a bigger T.

So these relationships are fundamental relationships of factoring and quadratic residues. They were always there.

It is so wild.

The answers are there it's just that where they show up depends on 'a' and the actual answer for k. It's kind of strange but you can watch the mathematics shifting things around to handle each issue presented by the 4 constraints when it gives the answer.

But yeah, it's mathematics, so it has infinite intelligence, so it's not like it actually DOES anything as these answers are logically built into numbers already.

Wild. Just wild.