Harristotelian Logic

Here's a post to go over the latest with my factoring research and explain a key breakthrough, as well as address the issue of demonstration.

First some background, since August of last year I have focused on very simple congruences in an attempt to develop an integer factorization method, where now I present as

y^2 = x^2 mod T

which is of course the difference of squares with T the target prime, and the one addition I make is introducing a variable I call k, where

k = 2x mod T

which is the second congruence. That equation I multiply by k and then add to the first, so that I can complete the square and since I'm moving to actually using it, I go to an explicit equation with

(x+k)^2 = y^2 + 2k^2 + n*T

where n is some non-zero integer, and I have had the gist of that in various form as I've puzzled over it and tried to get it to work well for about a year now, but I'm talking a lot about this now so what's new?

The answer is that my various attempts at analysis have not explained exactly when and why this system works when it does, and why it might NOT work, like, how do you pick k and n which are the variables you must choose and the only variables that you can fiddle with as you try to factor the target composite T?

So two key variables where if you pick them correctly you factor the target T non-trivially, but how do you choose?

The breakthrough came when I focused on a hypothetical T that is made up of two primes:

T = p_1*p_2

where the p's are differing primes, and wondered about picking x, and in that way choose k, and I found that with that hypothetical choice there were two more key equations that stepped in:

x+y = c_1*p_1 and x-y = c_2*p_2

solving the difference of squares where the c's are non-zero integers, so I can just solve for x and y to get

2x = c_1*p_1 + c_2*p_2

from which I have c_1 = (2x)*(p_1)^{-1} mod p_2, so you can pick ANY non-zero x coprime to p_1 and p_2,

and get a solution as then you have

y = (c_1*p_1 - c_2*p_2)/2

and importantly since c_2*p_2 is subtracted in one case and added in another it must be true that either x or y is at least the size of c_1*p_1, so how big can c_1 get?

Well c_1 = (2x)*(p_1)^{-1} mod p_2, tells us that its maximum is the largest residue available mod p_2 which is

p_2 - 1

so it must be true that abs(c_1)<abs(2x*p_2), so

abs(c_1*p_1)<abs(2x*p_2*_1) < abs(2x*T)

which is a crucial result, showing that it is the choice of x that is key.

So now, of course, it pays to look at the solution for x and y from

(x+k)^2 = y^2 + 2k^2 + n*T

more carefully, so introducing f_1 and f_2 where

4f_1*f_2 = 2k^2 + n*T

I have that y = f_1 - f_2 and x = f_1 + f_2 - k.

So I have a way to roughly estimate the size necessary for 2k^2 + n*T, as it has got to be rather large if either of the prime factors are large since x or y must be as large as c_1*p_1.

I think that it wouldn't be hard to generalize to a composite with an arbitrary number of primes, but for now getting an explanation is key so that can left for clean-up later.

In the past year, I have worked with various algorithms programmed in Java as I've tried to get the equations to work, and puzzled over their behavior, but now have an explanation for that behavior as I used to do things like let k=floor(T/30) which would have made x move about in some random way.

But how is this result relevant to that? Well if I pick a k and n that makes 2k^2 + n*T too small then the primary congruences:

y^2 = x^2 mod T and k = 2x mod T

are NOT satisfied which is what I call decoupling.

The best guess now for picking k is to pick k=2, corresponding to x = 1 mod T.

Savvy readers may note that the mathematics CAN also give you a non-trivial factorization if with

T = p*C

where p is a prime and C is a composite:

y^2 = x^2 mod p and k = 2x mod p

where the size limit would still come into play but would be 2x*p, and I have an example of such a factorization that I did before when I was still puzzling over how to pick k:

T = 732367903, k=floor(T/30) = 24412263, n= -2

2k^2 + n*T = 1191915704826532 = ( 2^2 )( 7 )( 73 )( 583129014103 )

f_1 = 7/2 and f_2 = 85136836059038

y=-170273672118069/2 and x=170273623293557/2

so, x+y=-24412256, which has 223 as a factor.

T = 732367903 = (223)(3284161).

Notice that you get the target factored with a trivial factorization of 2k^2 + n*T, which remarkably enough is just a bit larger than 2x*T.

So why does this matter?

Well, if you are over the minimums then there could be a very high probability of a non-trivial factorization while if you are BELOW the minimums there is a 0% probability of factoring—the equations decouple—so it's an absolute cut-off.

Above the minimums the mathematics goes looping through possible values for

2x = c_1*p_1 + c_2*p_2

and

y = (c_1*p_1 - c_2*p_2)/2

where it has infinity, so with your choice of k, you force possible x's and those force the math to go looking for c's that will give you a y for the size of abs(2k^2 + n*T) that you have.

If none exists, then you are decoupled.

But of course you can increase that size by increasing abs(n) as you can ONLY move in increments or decrements of T itself.

If a solution does exist then you have a non-trivial factorization.

Oh yeah, so if it's so great why can't I factor some huge number?

Well, I just got an explanation of mathematical behavior which I've puzzled over for a year and JUST got that explanation a couple of days ago.

So I'm musing over it. To me mathematics is a joy and these kind of searches are fun and I like to talk about them, but yes factoring is serious business as well so understandably some people would like me to produce some spectacular factorization now early in the research phase.

But that is what people who don't understand basic research often ask of researchers.

It's human nature to want something definite as early as possible, but the reality of real research that answers of practical importance, especially for business reasons, often take some time to reach.