JSH: Iterative process, factoring

To me it's just such a remarkable journey to do basic mathematical
research where you start with a concept and look to figure out the
mathematics that says the concept is viable or it's not.  And today we
have advantages that just were not on this planet before.  Modern
problem solving techniques are just so much more powerful than what
was known in the past when researchers were often more like hobbyists
like Fermat or introducing new systems like Newton, whereas today, the
science and art of problem solving is fully matured.

It only makes sense that people using the best techniques of our
modern era can figure out extraordinary things.

I've been trained to use iterative processes and brainstorming so the
oddity of the posting style that I use is easily explained as throwing
ideas out there as part of brainstorming, and there is usually a
progression through a fairly structured process to each iteration.

With factoring after considering what was previously known I asked
myself, can you maybe factor one number by using the factorization of
some other number?

And that was just a question, which became a concept I called
surrogate factoring and that start was over 4 years ago.

I've talked to people who are amazed that you can work on a math
problem for years, but for readers on these forums it should not, of
course, sound all that remarkable.  What is I think remarkable though
is the simple answer that years of iterations, with lots of
brainstorming, so many posts, so many false starts and so much
analysis has brought:

To solve for positive integer x, when x^2 = y^2 mod N, where N is an
odd target composite to be factored you can use helper primes to solve
the explicit equation:

x^2 = y^2 + cN

where c is an integer chosen to force cN mod 3 = 2, where for each
prime that works you will have

x^2 = 8^{-1}(9cN) mod p

where p is an odd prime that is less than 2x/3 for which the quadratic
residue exists, but further it must be true that the residue given by
a prime in that range for which a quadratic residue exists must give
an x near a value I call x_0 where x_0 is the largest positive integer
divisible by 3 such that

abs(cN - 8x_0^2/9)

is a minimum, and x must be within x_0/(3p) positive steps from x_0.

That the question of whether or not one factorization can lead to
another then has a surprising answer which represents the outcome of
over four years of basic research.

Weird thing is that the derivation of

x^2 = 8^{-1}(9cN) mod p

is easy to the point of trivial so I've presented it a lot (see other
threads), while the other rules are harder to explain so you'd have to
dig a bit to understand where they come from, where that last part
about x_0 is rather remarkable in terms of the why of the constraint.

I will say a few words about how I do problem solving which typically
does include some insults in a post, often lambasting the mathematical
community, which has a lot to do with motivating replies to my posts
so that I can get other people looking over mathematical ideas.  Years
of experience on newsgroups has taught me that conflict draws readers
and without it, you don't get readers at the same level.

Maybe unfortunate but it is the reality that I've found to be true in
my experiments with what works and what does not as that has been an
iterative process and a lot about problem solving as well.

If some other technique worked better, I'd use it.


James Harris