Harristotelian Logic

I finally am getting a handle on a crucial metric for determining how likely you are to factor using what I call surrogate factoring where if your target composite to factor is T, the following equations

x^2 = y^2 mod T

and

k = 2x mod T

can be used to derive

(x+k)^2 = y^2 + 2k^2 + nT

and by factoring 2k^2 + nT, you may factor your target composite.

I call 2k^2 + nT the surrogate, and also use S, for it.

S = 2k^2 + nT

The two big questions in the year since I came up with these simpler equations (note I usually wrote the second congruence as k^2 = 2xk mod T) have been, how effective can this be as a factoring method, and how do you pick k and n?

After trying various ideas over the last year or so I finally focused on assuming that T=p_1*p_2, where the p's are primes, and a solution to the congruence of squares:

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

and that was a crucial step allowing me to start answering questions about factoring probability and how to pick k and n.

A key relationship that emerged is

-(k+2xT)/T < m_1 < -(k + 2xp_1)/T

where the absolute value of m_1 is a count of non-trivial factorizations associated with p_2. Its partner is m_2 whose absolute value is a count of non-trivial factorizations associated with p_1.

So if both are non-zero the count of possible factorizations is abs(m_1*m_2). The key range shown tells you that a LARGE k is needed to give a large m_1. Of course you don't know p_1 if you're trying to factor but at least you can see how changing k impacts the range of possible factorizations.

Using the maximum for m_1, with a particular surrogate S, you can approximately find m_2:

m_2 > (S - k^2 - kT(4x + m_1) - (4x^2 + 2x*m_1)T^2)/(kT + T^2 + 2x*m_1*T^2)

Here x is not exactly known, but you have that the residue of x modulo T is (2)^{-1}k mod T. That is, the modular inverse of 2 modulo T times k. So x is just that plus or minus some multiple of T.

Now your choice of surrogate S means you have a choice of n, like an n you're guessing at but want to know the probability approximately before doing any factoring.

But you need one more n to make the range and that is given approximately by

n_min < -k^2/T + 4xk + 4x^2*T

where I call it n_min, though it may be larger than your other n, and you would need to make some educated guesses about x.

Now though finally you can get to an approximate probability with

abs(m_1*m_2/(n-n_min))*100%

where if either of the m's is 0, then you'd substitute 1 for that one.

Where I've assumed that the number of factorizations—given by abs(m_1*m_2)—spread evenly among n's.

Oh yeah, those equations are all for the probability that BOTH primes are factored out, but you can get a non-trivial factorization if only one is, which is like the math thinking T=p_1.

I won't go into detail about how that shifts all the equations but will just how how it shifts the key limit one:

-(k+2xT)/T < m_1 < -(k + 2xp_1)/T

becomes

-(k+2x*p_1)/p_1 < m_1 < -(k + 2x)/p_1

and, of course, you do not know what p_1 is so that equation is useful primarily to tell you how the size of k and x impact the number of possible factorizations, and the lesson is they need to both be BIG, but not as big as to get both primes at the same time.

Notice that in general the worst value for k is k=2, as with x=1 that gives

-2 < m_1 < 0

so you'd have just one possible factorization.

The research is fresh as I've just worked out most of this approach this week. But it is exciting to already have some key answers.

I have a page going into more detail at my Extreme Mathematics group:

http://groups.google.com/group/extrememathematics/web/integer-factorization