JSH: Understanding quadratic residues result
JSH
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.
James Harris